I'm working with NTT (Number theoretic transform) to reduce the complexity of a polynomial multiplication. For this, I'm using $P = 2^{64}-2^{32}+1$ to generate the primitive root $\omega_N$ needed by the transform.

This technique works for some values, but fails for others. E.g., for N = 4, values bigger than $2^{63}-2^{31}$ breaks the transform, so that $INTT(NTT(x)) \neq x$. This threshold gets smaller as N increases, and I don't understand why.

What defines the upper bound for the input in this transform?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.