From: Mark Wooding Date: Sat, 10 Feb 2007 22:47:20 +0000 (+0000) Subject: mp-jacobi: Implement Kronecker symbol. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/6791ed17a9a0436939061375131b0c643a4d182b 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 --- 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 --- 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 --- 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 {