0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

The answers to all your questions are yes, except the last one.

One can take $q$ to be nonprime, and use a ring. Under certain conditions this can enable you to evaluate the NTT for more general lengths $N.$

The number theoretic transform may be meaningful modulo $q$, even when the modulus is not prime, provided a principal root of order $N$ exist.

Examples are the Fermat Number Transform with $q= 2^k+1$ and Mersenne Number Transform with $q= 2^k-1$.

$\endgroup$
1
  • $\begingroup$ Thank you so much!! :) $\endgroup$
    – user15651
    May 3, 2022 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.