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.
55 lines
1.8 KiB
TeX
55 lines
1.8 KiB
TeX
\section{Montgomery Multiplication}
|
|
|
|
|
|
\subsection{The Problem}
|
|
|
|
Modular multiplication $a \cdot b \mod q$ requires division by $q$ (or equivalently,
|
|
computing the remainder). Division is slow---10--40 cycles on modern CPUs, compared to
|
|
3 cycles for multiplication.
|
|
|
|
\subsection{Montgomery's Trick}
|
|
|
|
Montgomery multiplication replaces division by $q$ with division by a power of 2 (which
|
|
is a free bit shift):
|
|
|
|
\begin{definition}[Montgomery Form]
|
|
The Montgomery representation of $a$ is $\tilde{a} = a \cdot R \pmod{q}$, where
|
|
$R = 2^k$ for some $k$ (typically $k = 16$ or $k = 32$).
|
|
\end{definition}
|
|
|
|
\begin{definition}[Montgomery Reduction]
|
|
Given $T < q \cdot R$, compute $T \cdot R^{-1} \pmod{q}$ without division by $q$:
|
|
\begin{enumerate}[nosep]
|
|
\item $m \leftarrow T \cdot q' \pmod{R}$ \quad (where $q' = -q^{-1} \pmod{R}$)
|
|
\item $t \leftarrow (T + m \cdot q) / R$ \quad (exact division, since $R \mid (T + mq)$)
|
|
\item If $t \geq q$, return $t - q$; else return $t$.
|
|
\end{enumerate}
|
|
\end{definition}
|
|
|
|
\begin{lstlisting}[language=Go,caption={Montgomery multiplication for $q = 3329$}]
|
|
const (
|
|
Q int32 = 3329
|
|
QInv int32 = 62209 // -Q^{-1} mod 2^16
|
|
RLog int32 = 16 // R = 2^16
|
|
)
|
|
|
|
// montgomeryReduce computes a * R^{-1} mod Q
|
|
func montgomeryReduce(a int32) int16 {
|
|
// Step 1: m = (a mod R) * QInv mod R
|
|
m := int16(a) * int16(QInv)
|
|
// Step 2: t = (a + m*Q) / R
|
|
t := (a + int32(m)*int32(Q)) >> RLog
|
|
return int16(t)
|
|
}
|
|
|
|
// montgomeryMul computes a * b * R^{-1} mod Q
|
|
func montgomeryMul(a, b int32) int32 {
|
|
return int32(montgomeryReduce(a * b))
|
|
}
|
|
\end{lstlisting}
|
|
|
|
The key: step 2 is an exact right shift, not a division. The entire operation uses
|
|
only multiplications and shifts---no division.
|
|
|
|
%% ============================================================
|