Sign up ×

I need your support.

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?

share|cite|improve this question
As in your previous question…, 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

Your Answer



Browse other questions tagged or ask your own question.