I understood how FFT works over complex field $\mathbb{C}$, but still do not understand why its variant Number Theoretic Transform (NTT) works over polynomial ring with some integer coefficient modulus as well.

Does anyone have some intuitions?


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.