Number Theoretic Transform

Generate primitive nth root of unity

r is the primitive nth root of unity iff there are not other numbers k divide n such that .
Use NthRootOfUnity function to generate the primitive nth root of unity.
NOTE: In my design, modulus must be prime.

TODO

Implement NTT algorithm under ideal.