papers/ntt-transform/sections/03-ntt-algorithm.tex

\section{NTT Algorithm}


\subsection{Cooley-Tukey Algorithm Adaptation}

The NTT computation follows the Cooley-Tukey FFT pattern, adapted for modular arithmetic. We present the iterative in-place algorithm that forms the basis of our optimized implementation.

\begin{algorithm}
\caption{Forward NTT (Iterative In-Place)}
\begin{algorithmic}[1]
\REQUIRE Vector $a \in \mathbb{Z}_q^n$, twiddle factors $\Psi_{\text{rev}}$
\ENSURE $a \leftarrow \text{NTT}(a)$ in bit-reversed order
\STATE $t \leftarrow n$
\FOR{$m = 1$ to $n-1$ step $2m$}
    \STATE $t \leftarrow t / 2$
    \FOR{$i = 0$ to $m-1$}
        \STATE $j_1 \leftarrow 2 \cdot i \cdot t$
        \STATE $j_2 \leftarrow j_1 + t - 1$
        \STATE $S \leftarrow \Psi_{\text{rev}}[m + i]$
        \FOR{$j = j_1$ to $j_2$}
            \STATE $U \leftarrow a[j]$
            \STATE $V \leftarrow a[j + t] \cdot S \bmod q$
            \STATE $a[j] \leftarrow (U + V) \bmod q$
            \STATE $a[j + t] \leftarrow (U - V) \bmod q$
        \ENDFOR
    \ENDFOR
\ENDFOR
\RETURN $a$
\end{algorithmic}
\end{algorithm}

\subsection{Butterfly Operations}

The core of NTT consists of butterfly operations that combine pairs of elements:

\begin{align}
a'[j] &= a[j] + \omega^k \cdot a[j + t] \bmod q \\
a'[j + t] &= a[j] - \omega^k \cdot a[j + t] \bmod q
\end{align}

Each butterfly requires:
\begin{itemize}
\item 1 modular multiplication
\item 2 modular additions/subtractions
\item 2 memory reads and 2 memory writes
\end{itemize}

For an $n$-element NTT, we perform $\frac{n}{2} \log_2 n$ butterflies.

\subsection{Twiddle Factor Precomputation}

Twiddle factors (powers of $\omega$ and $\psi$) are precomputed and stored in bit-reversed order to optimize memory access patterns:

\begin{lstlisting}[caption={Twiddle Factor Generation}]
function generateTwiddles(uint256 n, uint256 q, uint256 psi)
    returns (uint256[] memory) {
    uint256[] memory twiddles = new uint256[](n);
    twiddles[0] = 1;

    for (uint256 i = 1; i < n; i++) {
        uint256 j = bitReverse(i, log2(n));
        twiddles[j] = mulmod(twiddles[j-1], psi, q);
    }

    return twiddles;
}
\end{lstlisting}

\subsection{Bit-Reversal Permutation}

The NTT output is in bit-reversed order. For some applications (like pointwise multiplication), this ordering is advantageous and the reversal can be deferred.