1
$\begingroup$

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)$.

$\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.