\label{sec:mp-barrett}
P.~Barrett invented an elegant method for computing modular reductions. It
-requires a small amount of precomputation, depending only on the modulus $m$.
-Thereafter, it can compute residues mod $m$ using only multiplication and
+requires a small amount of precomputation, depending only on the modulus~$m$.
+Thereafter, it can compute residues mod~$m$ using only multiplication and
arithmetic shifts.
Montgomery's method (section~\ref{sec:mp-mont}, page~\pageref{sec:mp-mont})
initialized by calling \code{mpbarrett_create}
(page~\pageref{fn:mpbarrett-create}) and disposed of by
\code{mpbarrett_destroy} (page~\pageref{fn:mpbarrett-destroy}). A number
-less then $m^2$ may then be reduced modulo $m$ by passing it to
+less then~$m^2$ may then be reduced modulo~$m$ by passing it to
\code{mpbarrett_reduce} (page~\pageref{fn:mpbarrett-reduce}) along with the
appropriate reduction context.
which uses a simple square-and-multiply method combined with Barrett
reduction.
+\subsubsection{How it works}
+
+For brevity, let $b = 2^{\code{MPW_BITS}}$ be the base we're working in. Let
+$m$ be the modulus, and let $k$ be an integer such that $b^{k - 1} \le m <
+b^k$.
+
+The precomputation simply involves calculating $\mu = \lfloor b^{2k} / m
+\rfloor$. Hence, we have the bound on~$\mu$
+\begin{equation}
+ \frac{b^{2k}}{m} - 1 < \mu \le \frac{b^{2k}}{m}.
+ \label{eq:mpbarrett-mu-bound}
+\end{equation}
+
+Let $x$ be an integer such that $0 \le x < b^{2k}$. Firstly, let
+$q_0 = \lfloor x / b^{k - 1} \rfloor$. Thus,
+\begin{equation}
+ \frac{x}{b^{k - 1}} - 1 < q_0 \le \frac{x}{b^{k - 1}}.
+ \label{eq:mpbarrett-q0-bound}
+\end{equation}
+This division an be done simply by ignoring the least significant $k - 1$
+words in the representation of~$x$, requiring no computation.
+
+Next, calculate $q = \lfloor q_0 \mu / b^{k + 1} \rfloor$. The division can
+again be performed simply by ignoring the least significant $k + 1$ words of
+the result.
+
+Determining the bounds on $q$ is fairly easy, given
+equations \ref{eq:mpbarrett-mu-bound} and~\ref{eq:mpbarrett-q0-bound}.
+\[
+ \biggl\lfloor
+ \frac{(x / b^{k - 1} - 1)(b^{2k} \!/ m - 1) }{b^{k + 1}}
+ \biggr\rfloor
+ \le q \le
+ \biggl\lfloor \frac{(x / b^{k - 1})(b^{2k} \!/ m)}{b^{k + 1}} \biggr\rfloor
+\]
+Thus,
+\[
+ \biggl\lfloor
+ \frac{x}{m} - \frac{x}{b^{2k}} - \frac{b^{k - 1}}{m} + \frac{1}{b^{k + 1}}
+ \biggr\rfloor
+ \le q \le
+ \biggl\lfloor \frac{x}{m} \biggr\rfloor
+\]
+Since $b^{k - 1} \le m$ and $x < b^{2k}$, this can be reduced to simply
+\begin{equation}
+ \biggl\lfloor \frac{x}{m} \biggr\rfloor - 2
+ \le q \le
+ \biggl\lfloor \frac{x}{m} \biggr\rfloor
+ \label{eq:mpbarrett-q-bound}
+\end{equation}
+
+Finally, let $r = x - qm$.
+
+Firstly, because of the bounds on $q$ given in
+equation~\ref{eq:mpbarrett-q-bound}, we have
+\begin{equation}
+ x \bmod m \le r \le x \bmod m + 2m
+ \label{eq:mpbarrett-r-bound}
+\end{equation}
+Since $q$ is an integer, $r$ is equal to $x \bmod m + am$ where $a$ is $0$,
+$1$ or~$2$.
+
+Obviously, $r \le x \bmod m + 2m < 3m$. If $b > 3$, then
+$3 m < 3 b^k < b^{k + 1}$, because $m < b^k$. Hence the computation of $r$
+may be performed modulo $b^{k + 1}$, and in particular only the $k + 1$ least
+significant words of the product~$qm$ need be computed.
+
+The actual result $x \bmod m$ may be computed from $r$ by repeatedly
+subtracting $m$ while the result is still greater than $m$. The bound in
+equation~\ref{eq:mpbarrett-r-bound} shows that this need be done at most
+twice.
+
\subsubsection{The \code{mpbarrett_create} function}
\label{fn:mpbarrett-create}
\fsec{Description}
Initializes a Barrett reduction context $b$ suitable for performing
-reductions modulo $m$. The memory used by the context block must be provided
+reductions modulo~$m$. The memory used by the context block must be provided
by the caller, and must not be discarded until the context is destroyed.
The computation performed is as follows. Let $k = 2 \cdot |MP_LEN(|m|)|$.
\fsec{Description}
Calculates $x \bmod m$, where $m$ is the modulus configured into the Barrett
-reduction context $b$. The argument $d$ is a suggested destination.
+reduction context~$b$. The argument~$d$ is a suggested destination.
Note that not all values of $x$ are suitable for reduction: in particular,
negative values are improperly handled. Let $k = 2 \cdot |MP_LEN(|m|)|$;
then $x$ must be in the interval $[\,0, 2^{\code{MPW_BITS} \cdot k})$. It's
-probably safer (and eqsier) to ensure that $x < m^2$.
-
-For reference, the calculation works as follows:
-\begin{itemize}
-\item To simplify the notation, let $b = 2^{\code{MPW_BITS}}$.
-\item Let $q_0 = \lfloor x / b^{k - 1} \rfloor$. Let
- $q = \lfloor q_0 \mu / b^{k + 1} \rfloor$.
-\item Let $r = (x - q m) \bmod b^{k + 1}$.
-\item At this point, $r \equiv x \pmod m$, but $r$ may be too large. It can
- be reduced by repeated subtraction until it's in range.
-\end{itemize}
+probably safer (and easier) to ensure that $x < m^2$.
\fsec{Returns}
\fsec{Description}
Computes $x^e \bmod m$, where $m$ is the modulus configured into the Barrett
-reduction context $b$. The argument $d$ is a suggested destination.
+reduction context~$b$. The argument~$d$ is a suggested destination.
\fsec{Returns}
\begin{itemize}
\item Let $m$ be the modulus. Let $b$ be the radix used to represent
multiprecision integers. (In Catacomb, then, $b = 2^{\code{MPW_BITS}}$.)
- For Montgomery reduction to work, $m$ and $b$ must have no common factors.
-\item Let $R = b^n > m$ be the smallest power of $b$ which exceeds $m$.
+ For Montgomery reduction to work, $m$ and~$b$ must have no common factors.
+\item Let $R = b^n > m$ be the smallest power of $b$ which exceeds~$m$.
\item Precompute $m'$ such that $m m' \equiv -1 \pmod b$.
\item Precompute $R \bmod m$ and $R^2 \bmod m$, since these are generally
useful when using Montgomery's method.
Given $x < R^2$ and the above values, Montgomery's algorithm computes $\mont
x = x R^{-1} \bmod m$ efficiently, using only multiplications, additions and
word-sized shifts. The quantity $\mont x$ is called the \emph{Montgomery
-reduction of $x$}.
+reduction of~$x$}.
At first sight, this isn't particularly useful. However, an interesting
thing happens if you run an extra factor of $R$ all the way through your
\begin{description}
\def\makelabel#1{\code{#1}\hfil}
\item[mp *m] The modulus $m$ with which the reduction context is working.
-\item[mp *mi] The quantity $m'$ where $m m' \equiv -1
- \pmod{ 2^{\code{MPW_BITS}}}$.
-\item[size_t shift] The smallest integer $n$ such that
- $R = 2^{\code{MPW_BITS} \cdot n} > m$.
-\item[mp *r] The quantity $R \bmod m$. The Montgomery multiplicative
+\item[mp *mi] The integer $m'$ where $m m' \equiv -1 \pmod{R}$.
+\item[size_t n] The smallest integer $n$ such that $R = 2^{\code{MPW_BITS}
+ \cdot n} > m$.
+\item[mp *r] The integer $R \bmod m$. The Montgomery multiplicative
identity.
-\item[mp *r2] The quantity $R^2 \bmod m$.
+\item[mp *r2] The integer $R^2 \bmod m$.
\end{description}
All of these are set up by \code{mpmont_create} and should not be changed.
mpmont mm;
mpmont_create(&mm, m);
\end{listing}
-The next step is usually to multiply all of the inputs to the calculation by
-$R$. This is usually best done like this:
+The next step is usually to multiply all of the inputs to the calculation
+by~$R$. This is usually best done like this:
\begin{listing}
xr = mpmont_mul(&mm, MP_NEW, x, mm.r2);
\end{listing}
\subsubsection{How it works}
-Let $x_0$ be the integer we wish to reduce. Compute $u_1 = x_0 m' \bmod b$,
-and $v_1 = x_0 + u_1 m$.
+Let $x$ be the integer we wish to reduce. Compute $u = x m' \bmod R$, and
+$v = x + u m$.
-Obviously $u_1 = x_0 m' + bk$ for some integer $k$. So $v_1 = x_0 + u_1 m =
-x_0 + x_0 m m' + b k m$. Note that $m m' \equiv -1 \pmod b$; thus $m m' =
-b k' - 1$ for some $k'$, so $v_1$ then becomes $x_0(1 + bk' - 1) + b k m =
-b (k' x_0 + k m)$. Let $x_1 = v_1 / b = k' x_0 + k m$.
+Examining $v \bmod R$, we note that $v \equiv x + m m' x \equiv 0 \pmod R$,
+since $m m' \equiv -1 \pmod R$. Thus, $v$ is a multiple of $R$. Let $x' = v
+/ R$.
-Now note that $b k' = m m' + 1$, so $b k' \equiv 1 \pmod m$; hence, $k'
-\equiv b^{-1} \pmod m$. Thus $x_1 \equiv x_0 b^{-1} \pmod m$.
+Examining $x' \bmod m$ is slightly trickier. By definition, $u = x m' - k R$
+for some integer $k$. Then $v = x + m(x m' - k R)$, and $x' \equiv v R^{-1}
+\equiv x R^{-1} \pmod m$.
+Finally, if $x < m R$ to start with, $u < R$ and so $v < 2 m R$. Hence,
+$x' < 2 m$, so at most one subtraction of $m$ is enough to compute $x
+R^{-1} \bmod m$ from $x'$.
\subsubsection{The \code{mpmont_create} function}
\fsec{Description}
-Initializes a Montgomery reduction context $\mm$, using the given modulus
-$m$. The caller must provide memory for the context, and must ensure that
-the memory remains available until the context is destroyed.
+Initializes a Montgomery reduction context $\mm$, using the given
+modulus~$m$. The caller must provide memory for the context, and must ensure
+that the memory remains available until the context is destroyed.
If Catacomb is compiled with debugging support enabled, it will abort if $m$
is negative or even.
\fsec{Description}
-Performs a Montgomery reduction operation on the integer $x$, modulo $m$.
-The integer $d$ is a suggested destination.
+Performs a Montgomery reduction operation on the integer~$x$, modulo~$m$.
+The integer~$d$ is a suggested destination.
-For Montgomery reduction to work, $x$ must be less than $R^2$. In practice,
+For Montgomery reduction to work, $x$ must be less than~$mR$. In practice,
it's probably safest to ensure that $x < m^2$.
-This function is particularly efficient if $d = x$, i.e., if you overwrite
-$x$ with its Montgomery reduction.
+This function can be particularly efficient if $d = x$, i.e., if you
+overwrite $x$ with its Montgomery reduction.
\fsec{Returns}
\fsec{Description}
-Multiplies $x$ and $y$, and returns the Montgomery reduction of the product
+Multiplies $x$ and~$y$, and returns the Montgomery reduction of the product
modulo $m$. The integer $d$ is a suggested destination.
-Both $x$ and $y$ must be less than $R$, and it's probably safer in practice
+Both $x$ and~$y$ must be less than $R$, and it's probably safer in practice
if you ensure that $x, y < m$.
\fsec{Returns}
An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$.
-%%% Local Variables:
+%%% Local Variables:
%%% mode: latex
%%% TeX-master: "catacomb"
-%%% End:
+%%% End:
projects / u / mdw / catacomb / blobdiff