implement for Z/NZ for general N

[jacksonwalters]

For an array or polynomial of size n, the key things that need to be generalized are inverting n and computing an nth root of unity omega.

Both depend on knowing the order of the multiplicative group, which is given by the Euler totient function \phi(N).

\phi(p) = p-1 for p prime, and \phi(p^2) = p(p-1)

In general, \phi(N) depends on the factorization of N. There is probably a library to compute this.

Then omega = g^{\phi(N)/n} for a primitive root of unity g mod N, and n^{-1} = n^{\phi(N) - 1} mod N.

[jacksonwalters]

https://docs.rs/reikna/latest/reikna/totient/index.html