I was learning the topic FFT from e-maxx.ru (translated version). The english translation for this part "The discrete Fourier transform in a modular arithmetic" is not very clear on google chrome. Also, I am not able to understand clearly the math behind it. Please someone explain it.
Also, I have one doubt regarding the generators in number theoretic transforms. I was going through this solution of this problem. I understood the editorial and how to solve it using fft. But in the NTT solution (given in link) the author discusses about generators for certain prime numbers in comments. Can you please elaborate what are generators and how to calculate them?
Thanks in advance.
**EDIT: ** Understood the concept.