+ * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
+ * @ax + by = gcd(a, b)@. This is useful for computing modular
+ * inverses. Neither @a@ nor @b@ may be zero.
+ */
+
+extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
+ mp */*a*/, mp */*b*/);
+
+/* -- @mp_modinv@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *x@ = argument
+ * @mp *p@ = modulus
+ *
+ * Returns: The inverse %$x^{-1} \bmod p$%.
+ *
+ * Use: Computes a modular inverse. An assertion fails if %$p$%
+ * has no inverse.
+ */
+
+extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/);
+
+/* --- @mp_jacobi@ --- *
+ *
+ * Arguments: @mp *a@ = an integer
+ * @mp *n@ = another integer
+ *
+ * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
+ *
+ * Use: Computes the Kronecker symbol %$\jacobi{a}{n}$%. If @n@ is
+ * prime, this is the Legendre symbol and is equal to 1 if and
+ * only if @a@ is a quadratic residue mod @n@. The result is
+ * zero if and only if @a@ and @n@ have a common factor greater
+ * than one.
+ *
+ * If @n@ is composite, then this computes the Kronecker symbol
+ *
+ * %$\jacobi{a}{n}=\jacobi{a}{u}\prod_i\jacobi{a}{p_i}^{e_i}$%
+ *
+ * where %$n = u p_0^{e_0} \ldots p_{n-1}^{e_{n-1}}$% is the
+ * prime factorization of %$n$%. The missing bits are:
+ *
+ * * %$\jacobi{a}{1} = 1$%;
+ * * %$\jacobi{a}{-1} = 1$% if @a@ is negative, or 1 if
+ * positive;
+ * * %$\jacobi{a}{0} = 0$%;
+ * * %$\jacobi{a}{2}$ is 0 if @a@ is even, 1 if @a@ is
+ * congruent to 1 or 7 (mod 8), or %$-1$% otherwise.
+ *
+ * If %$n$% is positive and odd, then this is the Jacobi
+ * symbol. (The Kronecker symbol is a consistant domain
+ * extension; the Jacobi symbol was implemented first, and the
+ * name stuck.)
+ */
+
+extern int mp_jacobi(mp */*a*/, mp */*n*/);
+
+/* --- @mp_modsqrt@ --- *
+ *
+ * Arguments: @mp *d@ = destination integer
+ * @mp *a@ = source integer
+ * @mp *p@ = modulus (must be prime)
+ *
+ * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else
+ * a null pointer.
+ *
+ * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%,
+ * if one exists; else a null pointer. This function will not
+ * work if %$p$% is composite: you must factor the modulus, take
+ * a square root mod each factor, and recombine the results
+ * using the Chinese Remainder Theorem.
+ *
+ * We guarantee that the square root returned is the smallest
+ * one (i.e., the `positive' square root).