Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol introduced by Jacobi in 1837 [C.G.J.Jacobi "Uber die Kreisteilung und ihre Anwendung auf die Zahlentheorie", "Bericht Ak. Wiss. Berlin" (1837) pp 127-136] . It is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

Motivation

The Legendre symbol $(\; frac\{a\}\{p\})$ is defined for all integers "a" and all odd primes "p" by

:

If $(\; frac\{a\}\{p\})$ = 1, "a" is called a quadratic residue (mod "p"). If $(\; frac\{a\}\{p\})$ = −1, "a" is called a quadratic nonresidue (mod "p").
Zero is usually treated as a special case.

The by-hand algorithms used in the 19th century for primality testing and factorizing [Gauss, DA arts 329-334.] , and also many calculations needed for the ongoing development of algebraic number theory, required the calculation of numerous Legendre symbols.

There is a formula for the Legendre symbol called Euler's criterion: $left(frac\{a\}\{p\}\; ight)\; equiv\; a^\{(p-1)/2\}pmod\{p\}.$

$mbox\{Problem:\; Given\; that\; 9907\; is\; prime,\; calculate\; \}left(frac\{1001\}\{9907\}\; ight).$

Although relatively easy today, calculating :$left(frac\{1001\}\{9907\}\; ight)\; equiv\; 1001^\{4953\}\; pmod\{9907\}$ by hand (even with a mechanical calculator) is not very practical. [Gauss, DA, art. 106 says it's useless if the numbers are at all large.] [Euler's criterion takes O(log³ "n") steps. Bach & Shallit, p. 122] Using the most efficient modern powering algorithms, the example requires a dozen or so multiplies of four-digit numbers, and as many divisions by 9907. It's too laborious to be practical when the numbers are larger than a few million.

Now the Legendre symbol obeys a couple of rules

:$left(frac\{ab\}\{p\}\; ight)\; =\; left(frac\{a\}\{p\}\; ight)left(frac\{b\}\{p\}\; ight)mbox\{,\; so\; \}\; left(frac\{a^2\}\{p\}\; ight)=1mbox\{\; (or\; \}0mbox\{)\}$

:$mbox\{If\; \}a\; equiv\; b\; pmod\{p\},left(frac\{a\}\{p\}\; ight)\; =\; left(frac\{b\}\{p\}\; ight)$

that are easily deduced from its definition, and also the law of quadratic reciprocity, (which isn't so easily deduced! ),

:$mbox\{if\; \}pmbox\{\; and\; \}qmbox\{\; are\; odd\; positive\; primes,\; \}left(frac\{p\}\{q\}\; ight)\; =\; left(frac\{q\}\{p\}\; ight)(-1)^\{frac\{(p-1)(q-1)\}\{4$

and its supplements

:

:

Calculations using the Legendre symbol

Calculation using these rules is "much" easier than raising a number to the 4953 ^rd power (mod 9907):

:$left(frac\{1001\}\{9907\}\; ight)\; =left(frac\{7\}\{9907\}\; ight)\; left(frac\{11\}\{9907\}\; ight)\; left(frac\{13\}\{9907\}\; ight).$

::$left(frac\{7\}\{9907\}\; ight)\; =-left(frac\{9907\}\{7\}\; ight)\; =-left(frac\{2\}\{7\}\; ight)\; =-1$

::$left(frac\{11\}\{9907\}\; ight)\; =-left(frac\{9907\}\{11\}\; ight)\; =-left(frac\{7\}\{11\}\; ight)\; =left(frac\{11\}\{7\}\; ight)\; =left(frac\{4\}\{7\}\; ight)=1$

::$left(frac\{13\}\{9907\}\; ight)\; =left(frac\{9907\}\{13\}\; ight)\; =left(frac\{1\}\{13\}\; ight)=1$

:$left(frac\{1001\}\{9907\}\; ight)\; =-1$

That was fun. Now calculate $left(frac\{2183\}\{9907\}\; ight).$

The first step is finding that 2183 = 59 × 37. Before electronic computers, factorizing numbers "really" slowed down calculations and even today, if the numbers involved are at all large, factorization is a fairly slow process. For arbitrary [I.e, not Fermat numbers or Mersenne numbers or something of the sort for which there are special algorithms] numbers bigger than a few hundred digits it is impossible with known [Don't forget that WWII British Intelligence had Alan Turing on the codebreaking staff.] hardware and algorithms.

:$left(frac\{2183\}\{9907\}\; ight)\; =left(frac\{59\}\{9907\}\; ight)\; left(frac\{37\}\{9907\}\; ight).$

::$left(frac\{59\}\{9907\}\; ight)\; =-left(frac\{9907\}\{59\}\; ight)\; =-left(frac\{54\}\{59\}\; ight)\; =-left(frac\{2\}\{59\}\; ight)\; left(frac\{27\}\{59\}\; ight)\; =left(frac\{27\}\{59\}\; ight)$

:::$=-left(frac\{59\}\{27\}\; ight)\; =-left(frac\{5\}\{27\}\; ight)\; =-left(frac\{2\}\{5\}\; ight)\; =1$

::$left(frac\{37\}\{9907\}\; ight)\; =left(frac\{9907\}\{37\}\; ight)\; =left(frac\{9\}\{37\}\; ight)\; =1$

:$left(frac\{2183\}\{9907\}\; ight)\; =1.$

Of course, it is possible that some of the numbers in the intermediate steps would need to be factorized as well. What Jacobi discovered was a way to calculate the Legendre symbol without factorizing any numbers.

Definition

For any integer "a" and any positive odd integer "n" the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of "n":

:$Bigg(frac\{a\}\{n\}Bigg)\; =\; left(frac\{a\}\{p\_1\}\; ight)^\{alpha\_1\}left(frac\{a\}\{p\_2\}\; ight)^\{alpha\_2\}cdots\; left(frac\{a\}\{p\_k\}\; ight)^\{alpha\_k\}mbox\{\; where\; \}\; n=p\_1^\{alpha\_1\}p\_2^\{alpha\_2\}cdots\; p\_k^\{alpha\_k\}$

Following the normal convention for the empty product, $Bigg(frac\{a\}\{1\}Bigg)\; =\; 1.$

Properties of the Jacobi symbol

These facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol. [Almost any textbook on elementary number theory, e.g. Ireland & Rosen pp 56-57]

:$mbox\{If\; \}\; nmbox\{\; is\; an\; odd\; prime,\; then\; the\; Jacobi\; symbol\; \}\; left(frac\{a\}\{n\}\; ight)\; mbox\{\; is\; also\; a\; Legendre\; symbol.\}$

:

\pm1mbox{ if } gcd(a,n) = 1end{cases}

:$left(frac\{ab\}\{n\}\; ight)\; =\; Bigg(frac\{a\}\{n\}Bigg)left(frac\{b\}\{n\}\; ight)\; mbox\{,\; so\; \}left(frac\{a^2\}\{n\}\; ight)\; =\; 1\; mbox\{\; (or\; \}\; 0\; mbox\{)\}$

:$left(frac\{a\}\{mn\}\; ight)=left(frac\{a\}\{m\}\; ight)left(frac\{a\}\{n\}\; ight)mbox\{,\; so\; \}left(frac\{a\}\{n^2\}\; ight)\; =\; 1\; mbox\{\; (or\; \}\; 0\; mbox\{)\}$

:$mbox\{If\; \}a\; equiv\; b\; pmod\{n\},mbox\{\; then\; \}Bigg(frac\{a\}\{n\}Bigg)\; =\; left(frac\{b\}\{n\}\; ight)$

:$mbox\{If\; \}m\; mbox\{\; and\; \}\; n\; mbox\{\; are\; odd\; positive\; integers\; \}left(frac\{m\}\{n\}\; ight)\; =\; left(frac\{n\}\{m\}\; ight)(-1)^\{frac\{(m-1)(n-1)\}\{4$

:

:

Like the Legendre symbol,

:$mbox\{If\; \}left(frac\{a\}\{n\}\; ight)\; =\; -1mbox\{\; then\; \}a\; mbox\{\; is\; a\; quadratic\; nonresidue\; \}pmod\{n\}$

:$mbox\{If\; \}a\; mbox\{\; is\; a\; quadratic\; residue\; \}pmod\{n\}mbox\{\; then\; \}left(frac\{a\}\{n\}\; ight)\; =\; 1$

But, unlike the Legendre symbol

:$mbox\{If\; \}left(frac\{a\}\{n\}\; ight)\; =\; 1mbox\{\; then\; \}a\; mbox\{\; may\; or\; may\; not\; be\; a\; quadratic\; residue\; \}pmod\{n\}.$

This is because for "a" to be a residue (mod "n") it has to be a residue modulo "every" prime that divides "n", but for ("a"|"n") to = 1, it can be a non-residue modulo zero, two (or any even number) of the primes dividing "n".

The same calculations, using the Jacobi symbol

:$left(frac\{1001\}\{9907\}\; ight)\; =left(frac\{9907\}\{1001\}\; ight)\; =left(frac\{898\}\{1001\}\; ight)\; =left(frac\{2\}\{1001\}\; ight)left(frac\{449\}\{1001\}\; ight)=left(frac\{449\}\{1001\}\; ight)$

::$=left(frac\{1001\}\{449\}\; ight)\; =left(frac\{103\}\{449\}\; ight)\; =left(frac\{449\}\{103\}\; ight)\; =left(frac\{37\}\{103\}\; ight)\; =left(frac\{103\}\{37\}\; ight)$

::$=left(frac\{29\}\{37\}\; ight)\; =left(frac\{37\}\{29\}\; ight)\; =left(frac\{8\}\{29\}\; ight)\; =left(frac\{4\}\{29\}\; ight)left(frac\{2\}\{29\}\; ight)\; =-1.$

:$left(frac\{2183\}\{9907\}\; ight)\; =-left(frac\{9907\}\{2183\}\; ight)\; =-left(frac\{1175\}\{2183\}\; ight)\; =left(frac\{2183\}\{1175\}\; ight)\; =left(frac\{1008\}\{1175\}\; ight)$

::$=left(frac\{16\}\{1175\}\; ight)\; left(frac\{63\}\{1175\}\; ight)=left(frac\{63\}\{1175\}\; ight)\; =-left(frac\{1175\}\{63\}\; ight)\; =-left(frac\{41\}\{63\}\; ight)$

::$=-left(frac\{63\}\{41\}\; ight)\; =-left(frac\{22\}\{41\}\; ight)=-left(frac\{2\}\{41\}\; ight)left(frac\{11\}\{41\}\; ight)$

::$=-left(frac\{11\}\{41\}\; ight)\; =-left(frac\{41\}\{11\}\; ight)=-left(frac\{8\}\{11\}\; ight)=-left(frac\{4\}\{11\}\; ight)left(frac\{2\}\{11\}\; ight)=-left(frac\{2\}\{11\}\; ight)=1.$

The sequence where the top number is reduced modulo the bottom number, the top and bottom are switched, the top is reduced modulo the bottom, ... is what happens when the greatest common divisor is calculated using Euclid's algorithm, [The only real difference is the way even numbers are treated and the fact that the sign is flipped in the Jacobi calculation when both numbers are ≡ 3 (mod 4))] so calculating the Jacobi symbol (or the Legendre symbol if the bottom number is prime) is computationally exactly as hard as Euclid's algorithm. [ O(log "n" log "a") steps. Bach & Shallit p. 68 ff] (This shouldn't be surprising, since if ("a"|"b") = 0, gcd("a", "b") > 1.)

The facts that (2183|9907) = 1 and 9907 is prime imply that 2183 is a quadratic residue (mod 9907), but give no hint about what square it is congruent to. The Shanks-Tonelli algorithm is a way to find out. See Quadratic residue for more details.

908² ≡ 2183 (mod 9907).

Primality testing

There is another way the Jacobi and Legendre symbols differ. If the Euler criterion formula is used modulo a composite number, the result may or may not be the value of the Jacobi symbol.

So if it's not known whether a number "n" is prime or composite, we can pick a random number "a", calculate the Jacobi symbol ("a"|"n") and compare it with Euler's formula; if they differ, "n" is composite; if they're the same for many different values of "a", "n" is "probably prime".

This is the basis for the Solovay-Strassen probabilistic primality test and its refinement the Miller-Rabin test.

ee also

*The Kronecker symbol is a generalization of the Jacobi symbol to all integers.

Notes

References

*citation
last1 = Bach | first1 = Eric
last2 = Shallit | first2 = Jeffrey
title = Algorithmic Number Theory (Vol I: Efficient Algorithms)
publisher = The MIT Press
location = Cambridge
date = 1966
isbn = 0-262-02045-5

*citation
last1 = Lemmermeyer | first1 = Franz
title = Reciprocity Laws: from Euler to Eisenstein
publisher = Springer
location = Berlin
date = 2000
isbn = 3-540-66967-4

*citation
last1 = Ireland | first1 = Kenneth
last2 = Rosen | first2 = Michael
title = A Classical Introduction to Modern Number Theory (Second edition)
publisher = Springer
location = New York
date = 1990
isbn = 0-387-97329-X

*citation
last1 = Gauss | first1 = Carl Friedrich
last2 = Maser | first2 = H. (translator into German)
title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
publisher = Chelsea
location = New York
date = 1965
isbn = 0-8284-0191-8

*citation
last1 = Gauss | first1 = Carl Friedrich
last2 = Clarke | first2 = Arthur A. (translator into English)
title = Disquisitiones Arithemeticae (Second, corrected edition)
publisher = Springer
location = New York
date = 1986
isbn = 0387962549

External links

* [http://www.math.fau.edu/richman/jacobi.htm Calculate Jacobi symbol] gives a display like the ones in the examples.