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?