papers/lux-ntt-simd-implementation/sections/06-the-complete-ntt.tex

\section{The Complete NTT}


\begin{lstlisting}[language=Go,caption={Complete forward NTT in Go}]
// NTT performs the forward Number Theoretic Transform in-place.
// Input: polynomial in coefficient form.
// Output: polynomial in NTT/evaluation form.
func NTT(a *[256]int32) {
    k := 1
    for length := 128; length >= 2; length >>= 1 {
        for start := 0; start < 256; start += 2 * length {
            zeta := twiddles[k]
            k++
            for j := start; j < start+length; j++ {
                t := montgomeryMul(zeta, a[j+length])
                a[j+length] = a[j] - t
                a[j] = a[j] + t
            }
        }
    }
}

// INTT performs the inverse Number Theoretic Transform in-place.
func INTT(a *[256]int32) {
    k := 127
    for length := 2; length <= 128; length <<= 1 {
        for start := 0; start < 256; start += 2 * length {
            zeta := twiddlesInv[k]
            k--
            for j := start; j < start+length; j++ {
                t := a[j]
                a[j] = t + a[j+length]
                a[j+length] = montgomeryMul(zeta, t-a[j+length])
            }
        }
    }
    // Multiply by n^{-1}
    nInv := montgomeryForm(nInverse)
    for i := range a {
        a[i] = int32(montgomeryReduce(a[i] * nInv))
    }
}
\end{lstlisting}

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