+\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.
+
projects / u / mdw / catacomb / commitdiff