Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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