Module ntt 

Number Theoretic Transform for polynomial arithmetic. Number Theoretic Transform for ML-DSA (FIPS 204, Algorithms 41-45).

Implements the forward and inverse NTT over Z_q[X]/(X^256 + 1) with q = 8380417 and zeta = 1753 (a primitive 512th root of unity mod q). The NTT uses 8-bit reversal (BitRev_8) and goes all the way down to length-1 butterflies, so pointwise multiplication is simple element-wise multiplication.

Constants

ZETAS

Precomputed zeta table: ZETAS[k] = zeta^{BitRev_8(k)} mod q for k in 0..256.

Functions

mod_q

Reduce a modulo q to the range [0, q-1].

mul_mod_q

Modular multiplication: (a * b) mod q.

ntt

Forward NTT (Algorithm 41 of FIPS 204).

ntt_inv

pointwise_mul

Pointwise multiplication of two NTT-domain polynomials.

poly_add

Add two polynomials coefficient-wise, reducing each result modulo q.

poly_sub

Subtract two polynomials coefficient-wise, reducing each result modulo q.

to_mont_poly

Convert polynomial from /R to normal domain (multiply each coeff by R).