I am familiar with Fourier Transform and computing the DFT and FFT matrix for fast multiplication of integers. However, this is the first time I work with NTT applied to polynomial rings of the form $\mathbb{Z}_q[x]/x^{n} + 1$.
Say for small q=5 and $n$=2. My elements consists of all polynomials of degree at most $n-1$ with coefficients in $\mathbb{Z}_{q}$. All arithmetic of coefficients is done in $\mathbb{Z}_{q}$.
Now to obtain the $n$-th primitive root of unity $w$: I can express q = Nk + 1 = 22 + 1. I can let N=2 the NTT sample size and k=2. I let r = 2 (be a primitive root of q). I can compute w as $w = r^k \pmod{q}= 4 \pmod{5} = 4$
and confirm $w^{k} \equiv 1 \pmod{q}$. $4^{2} = 16 \pmod{q} = 1$
First question: this method to obtain $w$ is correct?
My 2 by 2 matrix would have this form:
\begin{matrix}
1 & 1\\
1 & w
\end{matrix}
Now, to consider higher powers of w, say we are working with larger ring and have a 3 by 3 matrix. Let NTT_matrix =
\begin{matrix}
1 & 1 & 1 \\
1 & w & w^2 \\
1 & w^2 & w^3 \\
\end{matrix}
Second question: to compute the backward matrix, Let NTT_inv_matrix =
\begin{matrix}
1 & 1 & 1 \\
1 & w & w^{-2} \\
1 & w^{-2} & w^{-3} \\
\end{matrix}
multiplied by $N^{-1}$.
To compute the negative powers of $w$, I can just take multiplicative inverse of the
corresponding element in the forward matrix and multiply them by $N^{-1}$ (the multiplicative inverse of the sample size $N$)?
So for example, say I have this entry in the forward matrix: $w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4$ The corresponding element in the backward matrix would be $w^-3$. To compute it, is the same as $(w^{3})^{-1}\pmod{5}$?
in this case the multiplicative inverse, MI, of $w^3\pmod{5}$ would also be 4 since $4*4 \equiv 1 \pmod{5}$. And the MI(N) in mod 5 is 3 since $3*2 \equiv 1 \pmod{5}$. So then, to compute $w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2$?
Third question:
So after I populate both matrices, I can multiply polynomials a(x) and b(x) by taking their coefficient tuples. For each polynomial, I proceed as follows:
If a(x) = x + 3 = (a1=1, a0=3) so its tuple is just v = (1, 3). I can apply transform via matrix-vector multiplication v*NTT_matrix = v. Same for b(x) say I get v2. Then v3 = v`*v2 and finally, answer = NTT_inv_matrix(v3). Correct?
Fourth question: This should give me the same answer as multiplying a(x)b(x) with the standard convolution formula correct ?
Fifth question, to define such a ring $\mathbb{Z}_q[x]/x^{n} + 1$, it is required that $q$ be prime to ensure a multiplicative inverse for all elements except 0, and also $x^{n} + 1$ must be irreducible in $\pmod{q}$, correct?
