A Complete Beginner Guide to the Number Theoretic Transform (NTT)

ePrint Report: A Complete Beginner Guide to the Number Theoretic Transform (NTT)

Ardianto Satriawan, Rella Mareta

The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity $O(n \log{n})$ instead of $O(n^2)$ when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm …

beginner cryptography encryption eprint report guide homomorphic encryption important ntt pqc quantum quantum cryptography report tool transform