Core engineering and protocols for Vectorized NTT Multiplication.
The core performance bottleneck of ML-KEM lies in the multiplication of polynomial matrices A in R_q^(k x k) by vectors s in R_q^k. By transforming polynomials into the NTT domain, multiplication is converted into 128 independent degree-1 polynomial products over Z_q[X]/(X^2 - zeta^(2i+1)). We vectorize these operations using 512-bit registers (AVX-512), processing 32 modular operations simultaneously.
Twiddle factors zeta^j are stored in Montgomery representation (zeta * 2^16 mod 3329). To prevent microarchitectural cache-bank conflicts, lookup tables are flattened and embedded directly into executable read-only data sections, ensuring zero variance in memory access latency regardless of input polynomial values.