NTT: Number theoretic transform

NTT implementation

Prerequsites:

• Complex arithmetic, in particular add/sub/mul, powers, roots and polar form

• Finite fields, with the same topics in mind

• Discrete Fourier transform

• Fast Fourier transform and in particular Cooley–Tukey FFT algorithm as N*logN algorithm implementing DFT

• Number-theoretic transform as FFT using the same add/sub/mul operations and rotts of 1, but in Galois field

Once you grasped all these topics, you can grab some FFT implementation and convert it to NTT.