# Minimal modulus for the finite field NTT

Suppose I am performing an NTT in a finite field $GF(p)$. I assume it contains the needed primitive root of unity.

I am using it to compute the convolution of two vectors of length $n=2^m, m\in \mathbb{N}$. As usual, I double the length of the vectors to $2n=2^{m+1}$ to make the convolution in fact acyclic (right? may be wrong here) and thus guarantee the exact interpolation of the product during INTT.

These vectors are in fact long integers, with all coefficients less than $BASE\in\mathbb{N}$. I wanted to come up with an inequality for the prime number $p$ so that the convolution is recoverable (i.e. equal to the real product of polynomials).

Here are my considerations:

The worst case is when all coefficients of the vectors are equal to $BASE-1$. Then the convolution coefficients are

$$c_0 = a_0 b_0 = (BASE-1)^2$$ $$c_1 = a_0 b_1 + a_1 b_0 = 2\cdot (BASE-1)^2$$ $$...$$ $$c_{n-1} = a_0 b_{n-1} + ... + a_{n-1} b_0 = n\cdot (BASE-1)^2$$ $$c_n = \underbrace{a_0 b_n}_{=0} + a_1 b_{n-1} + ... + a_{n-1} b_1 + \underbrace{a_n b_0 }_{=0} = (n-1)\cdot (BASE-1)^2$$ ... $$c_{2n-1}=0$$.

Thus I have come up with an inequality for the prime $p$:

$$n \cdot (BASE-1)^2 < p.$$

Does it guarantee that the convolution is computed correctly or have I missed something?

-
As in your previous question math.stackexchange.com/questions/134335/…, it would be useful if you indicated in your question the meaning of NTT (and INTT), i.e., the Fourier transform/inverse Fourier transform on a finite field. – KCd May 7 '12 at 14:01

The answer is yes. $n \cdot (BASE-1)^2 \leq p$ is indeed the biting inequality that needs to be satisfied.