papers/lux-lattice-cryptography-primer/sections/04-the-number-theoretic-transform.tex

\section{The Number Theoretic Transform}


Polynomial multiplication in $R_q$ is the bottleneck operation. Naive multiplication
is $O(n^2)$. The NTT reduces this to $O(n \log n)$.

\subsection{What Is NTT}

The NTT is the discrete Fourier transform over a finite field $\mathbb{Z}_q$ instead of
$\mathbb{C}$. It transforms a polynomial from coefficient representation to evaluation
representation (values at the $n$-th roots of unity in $\mathbb{Z}_q$).

\begin{definition}[NTT]
Given a polynomial $a(X) = \sum_{i=0}^{n-1} a_i X^i$ and a primitive $n$-th root of
unity $\omega \in \mathbb{Z}_q$:
\[
\hat{a}_j = \text{NTT}(a)_j = \sum_{i=0}^{n-1} a_i \omega^{ij} \pmod{q}
\]
\end{definition}

In evaluation representation, polynomial multiplication becomes pointwise:
\[
\text{NTT}(a \cdot b)_j = \text{NTT}(a)_j \cdot \text{NTT}(b)_j
\]

So: transform both polynomials ($2 \times O(n \log n)$), multiply pointwise ($O(n)$),
inverse-transform the result ($O(n \log n)$). Total: $O(n \log n)$.

\subsection{The Butterfly Operation}

The NTT is computed using the Cooley-Tukey butterfly, the same structure as the FFT:

\begin{lstlisting}[language=Go,caption={NTT butterfly operation in Go}]
// Butterfly: the core NTT operation
// In-place: a[j], a[j+step] are updated
func butterfly(a []uint32, j, step int, w uint32, q uint32) {
    t := mulmod(w, a[j+step], q)
    a[j+step] = submod(a[j], t, q)
    a[j] = addmod(a[j], t, q)
}

// Full NTT (iterative, in-place, Cooley-Tukey)
func NTT(a []uint32, omegas []uint32, q uint32) {
    n := len(a)
    bitReverse(a) // Reorder elements

    for step := 1; step < n; step <<= 1 {
        for j := 0; j < n; j += step << 1 {
            for k := 0; k < step; k++ {
                butterfly(a, j+k, step, omegas[step+k], q)
            }
        }
    }
}
\end{lstlisting}

\subsection{Montgomery Multiplication}

Modular multiplication ($a \cdot b \mod q$) is expensive because division is slow.
Montgomery multiplication avoids division by working in Montgomery form:

\begin{lstlisting}[language=Go,caption={Montgomery multiplication}]
const (
    Q     uint32 = 3329       // ML-KEM modulus
    QInv  uint32 = 62209      // Q^{-1} mod 2^16
    Mont  uint32 = 2285       // 2^16 mod Q (Montgomery constant)
)

// Montgomery reduction: given a < Q * 2^16,
// compute a * 2^{-16} mod Q without division
func montgomeryReduce(a uint32) uint16 {
    t := uint16(a) * uint16(QInv)
    return uint16((a - uint32(t)*uint32(Q)) >> 16)
}

// Multiply in Montgomery form
func mulMont(a, b uint16) uint16 {
    return montgomeryReduce(uint32(a) * uint32(b))
}
\end{lstlisting}

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