v0.1.9

updates the documentation. add some doctests.

v0.1.8

Resolves an overflow error for large primes such as q=12289.

v.0.1.6

We extend the NTT to the case of non prime power moduli. We require that n divide p-1 for each prime factor p of the given modulus.

This ensures we can compute an n^th root of unity mod modulus by computing n^th roots for each factor p^k and pulling them back using the Chinese remainder theorem.

v0.1.5

This version implements the NTT for prime power moduli p^k by computing the Euler totient function to compute the size of the multiplicative group. This allows us to compute a root of unity omega as well as invert n, generalizing the previous construction.

v.0.1.4

Performs the NTT (number theoretic transform) over a finite field F_p for prime p with multiplicative group of order p-1, as well as over the ring Z_{p^2} which has multiplicative group of order p^2-p.

Uses divide-and-conquer approach for O(n\log(n)) complexity.