Merge branch 'master' of git.distorted.org.uk:~mdw/publish/public-git/catacomb

[u/mdw/catacomb] / mp.h

diff --git a/mp.h b/mp.h
index 99ed098..13f97d1 100644 (file)
--- a/mp.h
+++ b/mp.h
@@ -941,15 +941,35 @@ extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/);
 
 /* --- @mp_jacobi@ --- *
  *
- * Arguments:  @mp *a@ = an integer less than @n@
- *             @mp *n@ = an odd integer
+ * Arguments:  @mp *a@ = an integer
+ *             @mp *n@ = another integer
  *
  * Returns:    @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
  *
- * Use:                Computes the Jacobi symbol.  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.
+ * 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*/);