papers/lux-ntt-simd-implementation/sections/02-mathematical-foundations.tex

\section{Mathematical Foundations}


\subsection{Roots of Unity in $\mathbb{Z}_q$}

A primitive $n$-th root of unity $\omega \in \mathbb{Z}_q$ satisfies $\omega^n \equiv 1
\pmod{q}$ and $\omega^k \not\equiv 1 \pmod{q}$ for $0 < k < n$. Such a root exists if
and only if $n \mid (q - 1)$.

For ML-KEM: $q = 3329$, $n = 256$. Since $3329 - 1 = 3328 = 2^8 \cdot 13$ and $256 = 2^8$,
we have $2^8 \mid (q - 1)$, so $256 \mid 3328$, confirming that a primitive 256th root of
unity exists.

For ML-DSA: $q = 8380417 = 2^{23} - 2^{13} + 1$, $n = 256$. Then $8380416 = 2^{13} \cdot 1023
= 2^{13} \cdot 3 \cdot 11 \cdot 31$, and since $2^8 \mid 2^{13}$ we have $256 \mid 8380416$,
confirming that a primitive 256th root of unity exists.

\subsection{The Forward Transform}

\begin{definition}[Forward NTT]
Given polynomial $a = (a_0, a_1, \ldots, a_{n-1})$ and primitive $2n$-th root of unity
$\zeta$ (so $\zeta^2$ is a primitive $n$-th root):
\[
\hat{a}_j = \sum_{i=0}^{n-1} a_i \cdot \zeta^{(2 \cdot \text{brv}(j) + 1) \cdot i} \pmod{q}
\]
where $\text{brv}(j)$ is the bit-reversal of $j$ in $\log_2(n)$ bits.
\end{definition}

In practice, we use the Cooley-Tukey decomposition which computes this via $\log_2(n)$
layers of butterfly operations.

\subsection{The Inverse Transform}

The inverse NTT (INTT) recovers coefficient form from evaluation form:
\[
a_i = n^{-1} \sum_{j=0}^{n-1} \hat{a}_j \cdot \zeta^{-(2 \cdot \text{brv}(j) + 1) \cdot i} \pmod{q}
\]

The factor $n^{-1}$ is the modular inverse of $n$ modulo $q$.

%% ============================================================