Doubt regarding NTT

I actually have an NTT(number theoretic transform) code of some user from some past contest,i wanted to modify it so that it could be work on my modulo.I tried by just changing the value of mod in the code,but it didnt gave right answer even for small inputs.Can someone tell where should i make the changes??

Thank you

The prime modulus defines the field of values you can work with. For each prime modulus the generators are different. If you only change the modulus, your previous n^{th} root of unity will probably not be a n^{th} root of unity in the new field (if you’re using the common Cooley-Tukey FFT, your n will be of the form 2^k).

Perhaps this link will be helpful: NTT

1 Like

Thank you sooo much!!That link was really helpful