Crate ntt

Functions

crt

the Chinese remainder theorem for two moduli

intt

Inverse transform using INTT, input bit-reversed

mod_exp

Modular exponentiation

ntt

Forward transform using NTT, output bit-reversed

omega

Compute n-th root of unity (omega) for p not necessarily prime

polymul

Naive polynomial multiplication

polymul_ntt

Multiply two polynomials using NTT (Number Theoretic Transform)

primitive_root

Fast computation of a primitive root mod p^e Computes a primitive root mod p and lifts it to p^e by adding successive powers of p

root_of_unity

computes an n^th root of unity modulo a composite modulus note we require that an n^th root of unity exists for each multiplicative group modulo p^e use the CRT isomorphism to pull back the list of n^th roots of unity to the composite modulus for the NTT, we require than a 2n^th root of unity exists

verify_root_of_unity

ensure the root of unity satisfies sum_{j=0}^{n-1} omega^{jk} = 0 for 1 \le k < n