2
$\begingroup$

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?

$\endgroup$

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.