mp-jacobi: Implement Kronecker symbol.

The Kronecker symbol is a generalization of the Jacobi symbol whose
domain is the entire space of integers.  This just lets us return
something vaguely sensible even when the arguments are messed up.

diff --git a/mp-jacobi.c b/mp-jacobi.c
index d0a67b6..3674f22 100644 (file)
--- a/mp-jacobi.c
+++ b/mp-jacobi.c
@@ -35,27 +35,88 @@
 
 /* --- @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.)
  */
 
 int mp_jacobi(mp *a, mp *n)
 {
   int s = 1;
+  size_t p2;
+
+  /* --- Handle zero specially --- *
+   *
+   * I can't find any specific statement for what to do when %$n = 0$%; PARI
+   * opts to set %$\jacobi{\pm1}{0} = \pm 1$% and %$\jacobi{a}{0} = 0$% for
+   * other %$a$%.
+   */
+
+  if (MP_ZEROP(n)) {
+    if (MP_EQ(a, MP_ONE)) return (+1);
+    else if (MP_EQ(a, MP_MONE)) return (-1);
+    else return (0);
+  }
+
+  /* --- Deal with powers of two --- *
+   *
+   * This implicitly takes a copy of %$n$%.  Copy %$a$% at the same time to
+   * make cleanup easier.
+   */
+
+  MP_COPY(a);
+  n = mp_odd(MP_NEW, n, &p2);
+  if (p2) {
+    if (MP_EVENP(a)) {
+      s = 0;
+      goto done;
+    } else if ((p2 & 1) && ((a->v[0] & 7) == 3 || (a->v[0] & 7) == 5))
+      s = -s;
+  }
+
+  /* --- Deal with negative %$n$% --- */
+
+  if (MP_NEGP(n)) {
+    n = mp_neg(n, n);
+    if (MP_NEGP(a))
+      s = -s;
+  }
+
+  /* --- Check for unit %$n$% --- */
 
-  assert(MP_ODDP(n));
+  if (MP_EQ(n, MP_ONE))
+    goto done;
 
-  /* --- Take copies of the arguments --- */
+  /* --- Reduce %$a$% modulo %$n$% --- */
 
-  a = MP_COPY(a);
-  n = MP_COPY(n);
+  if (MP_NEGP(a) || MP_CMP(a, >=, n))
+    mp_div(0, &a, a, n);
 
   /* --- Main recursive mess, flattened out into something nice --- */
 

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*/);

diff --git a/tests/mp b/tests/mp
index 14d73b9..1800fea 100644 (file)
--- a/tests/mp
+++ b/tests/mp
@@ -208,6 +208,62 @@ jacobi {
   6 7 -1;
   15 27 0;
   2132498039840981 98729378979237498798347932749951 1;
+  98729378979237498798347932749951 2132498039840981 1;
+
+  # --- Kronecker extension ---
+
+  0 0 0;
+  1 0 1;
+  -1 0 -1;
+  2 0 0;
+
+  2132498039840981 197458757958474997596695865499902 -1;
+  98729378979237498798347932749951 4264996079681962 1;
+  98729378979237498798347932749951 -4264996079681962 1;
+  -98729378979237498798347932749951 -4264996079681962 -1;
+
+  # --- Random tests made by PARI/gp ---
+
+  22 -19 -1;
+  48 -37 1;
+  -13 29 1;
+  -19 2 -1;
+  -43 31 1;
+  -12 -7 -1;
+  -14 -34 0;
+  -30 -29 -1;
+  25 26 1;
+  -27 20 -1;
+  -5 -45 0;
+  9 -42 0;
+  -51 -3 0;
+  -39 35 -1;
+  37 30 1;
+  13 18 -1;
+  -28 6 0;
+  -49 -15 1;
+  -1 1 1;
+  -9 13 1;
+  -47 44 -1;
+  -14 -30 0;
+  37 -36 1;
+  45 9 0;
+  -29 30 -1;
+  49 49 0;
+  -27 -10 -1;
+  -35 -25 0;
+  17 14 -1;
+  -35 29 1;
+  -1 33 1;
+  38 -11 1;
+  3 -24 0;
+  5 -25 0;
+  -31 22 -1;
+  40 30 0;
+  -43 26 -1;
+  -22 10 0;
+  11 -29 -1;
+  40 -18 0;
 }
 
 modsqrt {