mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
27 lines
798 B
TeX
27 lines
798 B
TeX
\section{Twiddle Factors}
|
|
|
|
|
|
The twiddle factors $\omega^k$ are precomputed and stored in a table. For NTT-256 with
|
|
$q = 3329$:
|
|
|
|
\begin{lstlisting}[language=Go,caption={Twiddle factor precomputation}]
|
|
func precomputeTwiddles(n int, zeta, q int32) []int32 {
|
|
twiddles := make([]int32, n)
|
|
twiddles[0] = toMontgomery(1, q) // zeta^0 = 1
|
|
|
|
zetaMont := toMontgomery(zeta, q)
|
|
for i := 1; i < n; i++ {
|
|
twiddles[i] = montgomeryMul(twiddles[i-1], zetaMont)
|
|
}
|
|
|
|
// Bit-reverse the twiddle table for in-order access
|
|
bitReverse(twiddles)
|
|
return twiddles
|
|
}
|
|
\end{lstlisting}
|
|
|
|
The bit-reversal ensures that twiddle factors are accessed in sequential order during the
|
|
NTT, which is optimal for cache performance.
|
|
|
|
%% ============================================================
|