NTT for fast multiplication of polynomials over a finite field, and the connection to polynomial evaluation

Question

Trying to code NTT and INTT in order to have faster polynomial multiplication. That has been extremely mind boggling for me.
The polynomials are over a finite field $GF(q)$.

I've already coded some version of NTT and INTT (according to Cooley-Tukey and Gentleman-Sande that I've found in some paper). I wanted to test match these methods to a simpler (and slower) version of my own. So I've coded some simple polynomial evaluation and interpolation of my own.

When I used parameters $n=128$ (polynomials up to the degree of $127$) $q=257$ (field size) $root=3$, I could see that the implementation of Cooley-Tukey indeed computed all evaluations of $root^{2i+1}$, although they were indexed differently in a bit-reverse-index-order. I realized these were actually evaluations of all $128$ numbers in the field with order of $256$. These are the primitive roots of unity.

Now I wished to apply it to larger $n=2^m$, but for this I need to enlarge $q$ as well. I've tried using $q=5003$ and the primitive-root $root=2$ (still with the same $n=128$). Now it seemed that the results of the NTT did not match my evaluations method. It simply did not calculate evaluations of $root^{2i+1}$ (in any order). By intuition, I've decided to pick another prime $q=15361$ with $root=10$ of order $256$. It resembles the other example from before because all the $128$ different values of $root^{2i+1}$ are of order $256$. Now it seemed to match my evaluations method, as I previously expected.

My questions are:
1. Is it necessary to pick such root whose order has to do something with the array's length? Or can the NTT and INTT compute the multiplication correctly even when the order of root is larger?
2. What do I get as output of the Cooley-Tukey NTT, if it's not the evaluations I thought they would be?
3. If I want the Cooley Tukey NTT to produce specific evaluations that I can test-match, what values of the field size $q$ must I choose, and then how can I fast generate a root to use? Which exponents of this root are then evaluated in the polynomial?

Answer 1

Ignoring all the details that go into making an efficient algorithm, the simplest version of the core algebraic idea here is that if $r$ is a primitive $n$-th root of unity in a field where $n$ is invertible, then you have the factorization

$$ x^n - 1 = \prod_{k=0}^{n-1} (x - r^k) $$

and furthermore, all of the factors on the right are relatively prime. So, by the polynomial version of the chinese remainder theorem, the following data for a polynomial $f(x)$ are equivalent:

• The reduced representative of $f(x)$ modulo $x^n - 1$
• The list of all reduced representatives of $f(x)$ modulo $x - r^k$

Reducing modulo a linear polynomial is just evaluation; so the following are equivalent:

• The reduced representative of $f(x)$ modulo $x^n - 1$
• The list of all values $f(r^k)$

A variation that often comes up in whole algorithms is to take advantage of the fact $-1$ is a very simple square root of unity and handle it separately, which amounts to needing a subroutine that handle the odd powers of $r$ separately:

$$ x^{n/2} + 1 = \prod_{k=1}^{n/2} (x - r^{2k-1}) $$

so that the following are equivalent:

• The reduced representative of $f(x)$ modulo $x^{n/2} + 1$
• The list of all values $f(r^{2k-1})$

The main computational part of the various transforms is all about converting back and forth between these two representations.

---

In short, yes, $r$ can't be arbitrarily chosen; it has to have a particular relationship to the calculation you're doing.