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.
41 lines
1.1 KiB
TeX
41 lines
1.1 KiB
TeX
\section{The Butterfly Operation}
|
|
|
|
|
|
\subsection{Cooley-Tukey Butterfly}
|
|
|
|
The Cooley-Tukey butterfly takes two inputs $(a, b)$ and a twiddle factor $\omega$, and
|
|
produces two outputs:
|
|
\begin{align}
|
|
a' &= a + \omega \cdot b \pmod{q} \\
|
|
b' &= a - \omega \cdot b \pmod{q}
|
|
\end{align}
|
|
|
|
\begin{lstlisting}[language=Go,caption={Cooley-Tukey butterfly in Go}]
|
|
// ctButterfly performs the Cooley-Tukey butterfly.
|
|
// a[i] and a[j] are updated in place.
|
|
// zeta is the twiddle factor in Montgomery form.
|
|
func ctButterfly(a []int32, i, j int, zeta int32) {
|
|
t := montgomeryMul(zeta, a[j])
|
|
a[j] = a[i] - t
|
|
a[i] = a[i] + t
|
|
}
|
|
\end{lstlisting}
|
|
|
|
\subsection{Gentleman-Sande Butterfly}
|
|
|
|
The inverse NTT uses the Gentleman-Sande butterfly:
|
|
\begin{align}
|
|
a' &= a + b \pmod{q} \\
|
|
b' &= (a - b) \cdot \omega^{-1} \pmod{q}
|
|
\end{align}
|
|
|
|
\begin{lstlisting}[language=Go,caption={Gentleman-Sande butterfly for INTT}]
|
|
func gsButterfly(a []int32, i, j int, zetaInv int32) {
|
|
t := a[i]
|
|
a[i] = t + a[j]
|
|
a[j] = montgomeryMul(zetaInv, t-a[j])
|
|
}
|
|
\end{lstlisting}
|
|
|
|
%% ============================================================
|