Difficulty in understanding Number Theoretic transform

Revision en2, by likecs, 2016-07-09 02:31:21

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.

Tags ntt, fft

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English likecs 2016-07-09 02:31:21 38 Tiny change: 'n advance.' -> 'n advance.\n\n**EDIT: ** Understood the concept.'
en1 English likecs 2016-07-07 22:00:33 821 Initial revision (published)