Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.