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

diff --git a/manual/mp-mp.tex b/manual/mp-mp.tex
index 4f3aa67..45d829f 100644
--- a/manual/mp-mp.tex
+++ b/manual/mp-mp.tex
@@ -64,8 +64,8 @@ more than once, which can otherwise lead to confusing bugs.
 
 \fsec{Returns}
 
-The number of words used in the representation of the integer $m$.  Note that
-the argument $m$ may be evaluated multiple times by this macro.
+The number of words used in the representation of the integer~$m$.  Note that
+the argument~$m$ may be evaluated multiple times by this macro.
 
 
 \subsubsection{The \code{mp_burn} function}
@@ -80,8 +80,8 @@ the argument $m$ may be evaluated multiple times by this macro.
 
 \fsec{Description}
 
-Sets the \code{MP_BURN} flag on the integer $m$.  Whenever memory associated
-with $m$, or results derived from it, is deallocated, it is overwritten with
+Sets the \code{MP_BURN} flag on the integer~$m$.  Whenever memory associated
+with~$m$, or results derived from it, is deallocated, it is overwritten with
 zeros to prevent traces being found in swap files or core dumps.
 
 
@@ -176,7 +176,7 @@ A pointer to a newly allocated multiprecision integer.
 
 \fsec{Description}
 
-Destroys the multiprecision integer $m$.  All resouces allocated to the
+Destroys the multiprecision integer~$m$.  All resouces allocated to the
 integer are freed.  It's most unusual for this to be the function you want:
 most of the time \code{mp_drop} (page~\pageref{fn:mp-drop}) is much more
 useful.
@@ -228,9 +228,9 @@ copying any data.\footnote{%
 
 \fsec{Description}
 
-The function \code{mp_copy} adds a reference to the multiprecision integer
-$m$.  The integer will not be destroyed until all references to it have been
-dropped.
+The function \code{mp_copy} adds a reference to the multiprecision
+integer~$m$.  The integer will not be destroyed until all references to it
+have been dropped.
 
 The macro \code{MP_COPY} performs exactly the same action as the
 \code{mp_copy} function, except that it uses inline code rather than a
@@ -239,7 +239,7 @@ function call.  It's probably smaller and faster than the function call too.
 \fsec{Returns}
 
 The address of the new reference.  This will usually be the same as the
-original argument $m$.
+original argument~$m$.
 
 \subsubsection{The \code{mp_drop} function and \code{MP_DROP} macro}
 \label{fn:mp-drop}
@@ -255,7 +255,7 @@ original argument $m$.
 \fsec{Description}
 
 The function \code{mp_drop} removes (`drops') a reference to the
-multiprecision integer $m$.  If there are no more references to the integer,
+multiprecision integer~$m$.  If there are no more references to the integer,
 it is destroyed, as if by \code{mp_destroy} (page~\pageref{fn:mp-destroy}).
 
 The macro \code{MP_DROP} performs exactly the same action as the
@@ -275,7 +275,7 @@ function call, so it's slightly faster but uses a little more code.
 
 \fsec{Description}
 
-If the integer $m$ has only one reference, the \code{mp_split} function
+If the integer~$m$ has only one reference, the \code{mp_split} function
 returns $m$ unchanged; otherwise, a copy is made and returned, and the
 reference count of $m$ is decremented.  Thus, either way, \code{mp_split}
 returns a pointer to an integer with the same value as $m$ and a single
@@ -284,7 +284,7 @@ refernce.  Thus, the result of \code{mp_split} is therefore safe to modify.
 The macro \code{MP_SPLIT} performs the same action as the \code{mp_split}
 function except that it uses inline code rather than a function call, and it
 modifies its argument in place rather than returning the new reference.  The
-macro \code{MP_SPLIT} may evaluate its argument $m$ multiple times.
+macro \code{MP_SPLIT} may evaluate its argument~$m$ multiple times.
 
 \fsec{Returns}
 
@@ -310,32 +310,32 @@ The actual behaviour is complicated:
 
 \begin{itemize}
 \item If $m$ is equal to \code{MP_NEW}, or the \code{MP_CONST} flag is set on
-  $m$, then allocate a new integer $d$ of size $\sz$ by calling
+  $m$, then allocate a new integer~$d$ of size $\sz$ by calling
   \code{mp_create} (page~\pageref{fn:mp-create}).
 \item Otherwise, if $m$ has more than one reference, a reference is removed
   asif by \code{mp_drop} (page~\pageref{fn:mp-drop}) and a new integer $d$ of
   size $\sz$ is allocated as if by \code{mp_create}.
-\item Otherwise, the integer $m$ is extended to $\sz$ words, as if by calling
-  \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal to
-  $m$.
+\item Otherwise, the integer~$m$ is extended to $\sz$ words, as if by calling
+  \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal
+  to~$m$.
 \end{itemize}
 
 The resulting integer $d$ is returned from the function.
 
 The upshot of all of this is that $d$ has exactly one reference, space for
-$\sz$ words of data, and no particular value set.  Any other references to
-the original integer $m$ (whether counted or not) continue to refer to the
-same value.  The total number of references to $d$ and $m$ after
+$\sz$~words of data, and no particular value set.  Any other references to
+the original integer~$m$ (whether counted or not) continue to refer to the
+same value.  The total number of references to $d$ and~$m$ after
 \code{mp_modify} returns is equal to the initial number of references to $m$
 before the call.
 
 The macro \code{MP_MODIFY} does the same job using inline code; it sets $m$
-to the new integer $d$ when it's finished.  The macro expands to a fairly
+to the new integer~$d$ when it's finished.  The macro expands to a fairly
 large chunk of code.
 
 \fsec{Returns}
 
-The function \code{mp_modify} returns the destination integer $d$ as
+The function \code{mp_modify} returns the destination integer~$d$ as
 described above.
 
 
@@ -359,9 +359,9 @@ of a multiprecision integer.
 \fsec{Description}
 
 The function \code{mp_resize} resizes the array used to hold the value of the
-integer $m$ such that it has space for $\sz$ words.  No check is made to see
+integer~$m$ such that it has space for $\sz$ words.  No check is made to see
 whether $m$'s array is already the correct size.  The integer's array limit
-pointer \code{vl} is set to point $\sz$ words higher than the base pointer
+pointer \code{vl} is set to point $\sz$~words higher than the base pointer
 \code{v}.
 
 The macro \code{MP_RESIZE} performs exactly the same action as the
@@ -427,7 +427,7 @@ The macro \code{MP_SHRINK} performs exactly the same operation as
 
 \fsec{Description}
 
-Minimizes the amount of memory used by the represenation of the integer $m$.
+Minimizes the amount of memory used by the represenation of the integer~$m$.
 This isn't usually useful unless $m$ is going to remain constant for a long
 time, or has become extremely large for some reason.
 
@@ -444,6 +444,102 @@ time, or has become extremely large for some reason.
 \subsection{More advanced algorithms}
 \label{sec:mp-adv}
 
+\subsubsection{The \code{mp_gcd} function}
+\label{fn:mp-gcd}
+
+\fsec{Synopsis}
+
+\begin{listinglist}
+|#include <catacomb/mp.h>| \\
+|void mp_gcd(mp **|$g$|, mp **|$a$|, mp **|$b$|, mp *|$x$|, mp *|$y$|);|
+\end{listinglist}
+
+\fsec{Description}
+
+The function \code{mp_gcd} implements an `extended GCD' algorithm.  Given
+integers $x$ and~$y$, it computes integers $g$, $a$, and~$b$ such that $g =
+\gcd(x, y)$ is the greatest common divisor of $x$ and $y$, and $ax + by = g$.
+
+If the arguments $g$, $a$ or~$b$ are null pointers, the appropriate result is
+discarded; otherwise, the current value of $|*|g$, $|*|a$ or $|*|b$ is used
+as a suggested destination for the result, and replaced by the actual result.
+
+If both $a$ and~$b$ are null, the results $a$ and $b$ are not computed.
+Hence \code{mp_gcd} can efficiently perform a simple greatest-common-divisor
+computation.
+
+A major use for \code{mp_gcd} is the calculation of modular inverses.  If
+$\gcd(x, n) = 1$ then \code{mp_gcd} computes integers $a$ and~$b$ such that
+$ax + bn = 1$, i.e., $ax \equiv 1 \pmod n$, so $a$ is the inverse of $x$,
+written $a \equiv x^{-1} \pmod n$.
+
+In order to better support this usage, \code{mp_gcd} implements a \emph{sign
+preference} system.  If only $a$ is requested, it will either be zero or
+have the same sign as~$y$; otherwise, $b$ will be zero or have the same sign
+as~$x$.  Thus, $x^{-1} \bmod n$ may be conveniently computed using the code
+\begin{listing}
+mp *xinv = MP_NEW;
+mp_gcd(0, 0, &xinv, n, x);
+\end{listing}
+(It's conventional to ensure that $x > y$, even though it doesn't actually
+make any difference.)
+
+The function \code{mp_gcd} works correctly for all integers $x$ and $y$.  The
+following properties of the results are guaranteed:
+\begin{itemize}
+  \unverb\|
+\item $\gcd(x, y) = \gcd(y, x)$ for all integers $x$ and~$y$.
+\item $\gcd(x, 0) = \gcd(0, x) = x$ for all integers~$x$.
+\item $|a| < |y|$, unless $y = 0$; similarly, $|b| < |x|$ if $x \ne 0$.
+\item If $x = y = 0$, then $a = b = 0$.  Otherwise, if $x = 0$, then $a = 0$
+  and $b = 1$; similarly, if $y = 0$, then $a = 1$ and $b = 0$.
+\end{itemize}
+
+\subsubsection{The \code{mp_jacobi} function}
+\label{fn:mp-jacobi}
+
+\fsec{Synopsis}
+
+\begin{listinglist}
+|#include <catacomb/mp.h>| \\
+|int mp_jacobi(mp *|$a$|, mp *|$n$|);|
+\end{listinglist}
+
+\fsec{Returns}
+
+The value of the  Jacobi symbol $\jacobi{a}{n}$.\footnote{%
+  Schneier writes the Jacobi symbol as $J(a, n)$.  The notation
+  $(\!\frac{a}{n}\!)$ seems more usual.} %
+The Jacobi symbol $\jacobi{a}{n}$ is defined for all integers~$a$ and odd
+integers~$n$ in terms of the Legendre symbol $\jacobi{a}{p}$ for prime~$p$,
+which is:
+\[
+  \jacobi{a}{p} = \begin{cases}
+     0 & if $a$ is a multiple of $p$ \\
+    -1 & if $a$ is a quadratic nonresidue mod $p$ \\
+     1 & if $a$ is a quadratic residue mod $p$
+   \end{cases}
+\]
+(An integer $x$ is a quadratic residue mod $n$ if and only if there exists an
+integer $y$ such that $y^2 \equiv x \pmod n$.  Note that $\jacobi{a}{p}
+\equiv a^{(p - 1)/2} \pmod p$.)
+
+The Jacobi symbol is defined as follows: let $p_0^{e_0} p_1^{e_1} \ldots
+p_k^{e_k} = n$ be the prime factors of $n$.  Then
+\[
+  \jacobi{a}{n} = \jacobi{a}{p_0}^{e_0} \jacobi{a}{p_1}^{e_1} \cdots
+    \jacobi{a}{p_k}^{e_k}
+\]
+Fortunately, the Jacobi symbol can be computed efficiently without factoring
+$n$ or performing modular exponentiations.
+
+The Jacobi symbol is used in the Solovay-Strassen primality test (not
+implemented in Catacomb -- the Rabin-Miller test is better), and in some
+subliminal channels in digital signature algorithms.
+
+The RSA public-key encryption algorithm leaks the Jacobi symbol of its
+plaintext.
+
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "catacomb"
