I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work.
Now I would like to implement multiplication of polynomials over finite fields $\mathbb{Z}_p[x]$ where $p$ is arbitrary prime number.
Does it changes anything that the coefficients are now bounded by $p$, compared to the former unbounded case?
In particular, original NTT required to find prime number $N$ as the working modulus that is larger than $(magnitude\ of\ largest\ element\ of\ input\ vector)^2 \times (length\ of\ input\ vector) + 1$ so that the result never overflows. If the result is going to be bounded by modulo that $p$ prime anyway, how small can the modulus be? Note that $p - 1$ does not have to be of form $(some\ positive\ integer) * (length\ of\ input\ vector)$.