\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}
\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.
\multicolumn{1}{c|}{\textbf{Value}} & \qquad &
\multicolumn{1}{c|}{\textbf{Constant}} &
\multicolumn{1}{c|}{\textbf{Value}} \\ \hlx{vc{1,2,4,5}v}
- MP_ZERO & 0 && MP_FOUR & 4 \\
- MP_ONE & 1 && MP_FIVE & 5 \\
- MP_TWO & 2 && MP_TEN & 10 \\
- MP_THREE & 3 && MP_MONE & -1 \\ \hlx{vc{1,2,4,5}}
+ MP_ZERO & 0 && MP_FOUR & 4 \\
+ MP_ONE & 1 && MP_FIVE & 5 \\
+ MP_TWO & 2 && MP_TEN & 10 \\
+ MP_THREE & 3 && MP_MONE & -1 \\ \hlx{vc{1,2,4,5}}
\end{tabular}
\goodbreak
\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.
\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
\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}
\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
\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
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}
\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.
\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
\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.
\subsection{More advanced algorithms}
\label{sec:mp-adv}
-%%% Local Variables:
+\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"
-%%% End:
+%%% End:
projects / u / mdw / catacomb / blobdiff