X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/3471ebd194145da52d419c6315459237b076e18d..3e248c3b5b309bc03eb5f70762d3f5671d51f996:/manual/mp-mod.tex

diff --git a/manual/mp-mod.tex b/manual/mp-mod.tex
index 6c04ec3..0904b50 100644
--- a/manual/mp-mod.tex
+++ b/manual/mp-mod.tex
@@ -12,8 +12,8 @@ performing modular arithmetic.
 \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})
@@ -26,7 +26,7 @@ The declarations required to use Barrett reduction are in
 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.
 
@@ -35,6 +35,78 @@ function \code{mpbarrett_exp} (page~\pageref{fn:mpbarrett-exp}) is provided
 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}
 
@@ -48,7 +120,7 @@ reduction.
 \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|)|$.
@@ -84,22 +156,12 @@ discarded.
 \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}
 
@@ -118,7 +180,7 @@ A value $d$ such that $0 \le d < m$ and $d \equiv x \pmod m$.
 \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}
 
@@ -133,8 +195,8 @@ reductions.  The method requires a number of values to be precomputed.
 \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.
@@ -142,7 +204,7 @@ reductions.  The method requires a number of values to be precomputed.
 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
@@ -179,13 +241,12 @@ members:
 \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.
 
@@ -217,8 +278,8 @@ initialized.  Suppose $m$ is the modulus we need to work with:
 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}
@@ -279,17 +340,20 @@ page~\pageref{sec:mp-barrett}).
 
 \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}
@@ -304,9 +368,9 @@ Now note that $b k' = m m' + 1$, so $b k' \equiv 1 \pmod m$; hence, $k'
 
 \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.
@@ -338,14 +402,14 @@ had acquired.
 
 \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}
 
@@ -363,17 +427,17 @@ An integer $d$ such that $0 \le d < m$ and $d R \equiv x \pmod m$.
 
 \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: