Jacobi symbol


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

:left(frac{a}{p} ight) = egin{cases};;,0mbox{ if } a equiv 0 pmod{p}\+1mbox{ if }a otequiv 0pmod{p} mbox{ and for some integer }x, ;aequiv x^2pmod{p}\-1mbox{ if there is no such } x. end{cases}

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(log3 "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

:left(frac{-1}{p} ight) = (-1)^{frac{(p-1)}{2 = left{egin{array}{cl} 1 & extrm{if};p equiv 1 pmod 4\ -1 & extrm{if};p equiv 3 pmod 4end{array} ight.

:{left(frac{2}{p} ight) = (-1)^{frac{(p^2-1)}{8 = left{egin{array}{cl} 1 & extrm{if};p equiv 1; extrm{ or };7 pmod 8\ -1 & extrm{if};p equiv 3; extrm{ or };5pmod 8end{array} ight.}

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.}

:left(frac{a}{n} ight) = egin{cases};;,0mbox{ if } gcd(a,n) e 1

\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

:left(frac{-1}{n} ight) = (-1)^{frac{(n-1)}{2 = left{egin{array}{cl} 1 & extrm{if};n equiv 1 pmod 4\ -1 & extrm{if};n equiv 3 pmod 4end{array} ight.

:{left(frac{2}{n} ight) = (-1)^{frac{(n^2-1)}{8 = left{egin{array}{cl} 1 & extrm{if};n equiv 1; extrm{ or };7 pmod 8\ -1 & extrm{if};n equiv 3; extrm{ or };5pmod 8end{array} ight.}

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.

9082 ≡ 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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Jacobi-Symbol — Das Jacobi Symbol, benannt nach Carl Gustav Jacob Jacobi, ist eine Verallgemeinerung des Legendre Symbols. Das Jacobi Symbol kann wiederum zum Kronecker Symbol verallgemeinert werden. Die Notation ist die gleiche wie die des Legendre Symbols:… …   Deutsch Wikipedia

  • Jacobi symbol — noun Mathematical function of two integers, written , based on whether a is a square modulo the prime factors of b …   Wiktionary

  • Jacobi — ist der Familienname folgender Personen: Abraham Jacobi (1830–1919), deutsch US amerikanischer Kinderarzt Albano von Jacobi (1854–1928), deutscher Offizier und Diplomat Ariane Jacobi (* 1966), deutsche Jazzsängerin und Moderatorin Arnold Jacobi… …   Deutsch Wikipedia

  • Symbol — des Sternbildes Löwe Der Terminus Symbol (aus dem Griechischen: Etwas Zusammengefügtes) oder auch Sinnbild wird im Allgemeinen für Bedeutungsträger (Zeichen, Wörter, Gegenstände, Vorgänge etc.) verwendet, die eine Vorstellung meinen (von etwas,… …   Deutsch Wikipedia

  • Jacobi sum — In mathematics, a Jacobi sum is a type of character sum formed with one or more Dirichlet characters. The simplest example would be for a Dirichlet character χ modulo a prime number p . Then take: J (χ) = Σ χ( a )χ(1 − a ) where the summation… …   Wikipedia

  • Jacobi triple product — In mathematics, the Jacobi triple product is a relation that re expresses the Jacobi theta function, normally written as a series, as a product. This relationship generalizes other results, such as the pentagonal number theorem.Let x and y be… …   Wikipedia

  • Jacobi polynomials — In mathematics, Jacobi polynomials are a class of orthogonal polynomials. They are obtained from hypergeometric series in cases where the series is in fact finite::P n^{(alpha,eta)}(z)=frac{(alpha+1) n}{n!}, 2F 1left(… …   Wikipedia

  • Legendre symbol — The Legendre symbol or quadratic character is a function introduced by Adrien Marie Legendre in 1798 [A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186] during his partly successful attempt to prove the law of quadratic… …   Wikipedia

  • Carl Gustav Jacob Jacobi — Carl Jacobi Carl Gustav Jacob Jacobi Born December 10, 1804(1804 …   Wikipedia

  • Carl Gustav Jacobi — Carl Jacobi Carl Gustav Jacob Jacobi (* 10. Dezember 1804 in Potsdam; † 18. Februar 1851 in Berlin), war ein deutscher Mathematiker. Er war ein Bruder von Hermann Jacobi. Jacobis Begabung für die Mathematik, aber auch für Sprachen, zeigte sich… …   Deutsch Wikipedia