Jacobi symbol: Information from Answers.com

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837,^[1] 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.

1 Definition
2 Properties
3 Calculating the Jacobi symbol
4 Example of calculations
- 4.1 Using the Legendre symbol
- 4.2 Using the Jacobi symbol
5 Primality testing
6 See also
7 Notes
8 References
9 External links

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}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k}\mbox{ where } n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

$(\tfrac{a}{p})$ represents the Legendre symbol, defined for all integers a and all odd primes p by

$\left(\frac{a}{p}\right) = \begin{cases} \;\;\,0\mbox{ if } a \equiv 0 \pmod{p} \\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, \;a\equiv x^2\pmod{p} \\-1\mbox{ if there is no such } x. \end{cases}$

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

Properties

These facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol.^[2]

Keep in mind that Jacobi symbols are only defined when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.

1) $\mbox{If } n\mbox{ is (an odd) prime, then the Jacobi symbol } \Bigg(\frac{a}{n}\Bigg) \mbox{ is also a Legendre symbol.}$

2) $\mbox{If }a \equiv b \pmod{n}\mbox{ then }\Bigg(\frac{a}{n}\Bigg) = \left(\frac{b}{n}\right)$

3) $\left(\frac{a}{n}\right) = \begin{cases} \;\;\,0\mbox{ if } \gcd(a,n) \ne 1 \\\pm1\mbox{ if } \gcd(a,n) = 1\end{cases}$

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

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

The law of quadratic reciprocity: if m and n are odd positive integers, then

6) $\left(\frac{m}{n}\right) = \left(\frac{n}{m}\right)(-1)^{\tfrac{m-1}{2}\tfrac{n-1}{2}} = \begin{cases} \;\;\;\left(\frac{n}{m}\right) & \text{if }n \equiv 1 \pmod 4 \text{ or } m \equiv 1 \pmod 4 \\ -\left(\frac{n}{m}\right) & \text{if }n\equiv m \equiv 3 \pmod 4 \end{cases}$

and its supplements

7) $\left(\frac{-1}{n}\right) = (-1)^\tfrac{n-1}{2} = \begin{cases} \;\;\,1 & \text{if }n \equiv 1 \pmod 4\\ -1 &\text{if }n \equiv 3 \pmod 4\end{cases}$

8) $\left(\frac{2}{n}\right) = (-1)^\tfrac{n^2-1}{8} = \begin{cases} \;\;\,1 & \text{if }n \equiv 1,7 \pmod 8\\ -1 &\text{if }n \equiv 3,5\pmod 8\end{cases}$

Like the Legendre symbol,

$\mbox{If } \left(\frac{a}{n}\right) = -1\mbox{ 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}\right) = 1$

But, unlike the Legendre symbol

$\mbox{If } \left(\frac{a}{n}\right) = 1 \mbox{ 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 the Jacobi symbol will equal one if a is a non-residue modulo zero, two (or any even number) of the primes dividing n.

Calculating the Jacobi symbol

The above formulas lead to an efficient^[3] algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the GCD of two numbers. (This should not be surprising in light of rule 3)).

The "numerator" is reduced modulo the "denominator" using rule 2). Any multiples of 2 are pulled out using rule 4) and calculated using rule 8). The symbol is flipped using rule 6), and the algorithm recurses until the "numerator" is 1 (covered by rule 4)) or 2 (covered by rule 8)), or the "numerator" equals the "denominator" (rule 3)).

Example of calculations

The Legendre symbol $(\tfrac{a}{p})$ is only defined for odd primes p. It obeys the same rules as the Jacobi symbol (i.e., reciprocity and the supplementary formulas for $(\tfrac{-1}{p})$ and $(\tfrac{2}{p})$ and multiplicativity of the "numerator".)

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

Using the Legendre symbol

$\left(\frac{1001}{9907}\right) =\left(\frac{7}{9907}\right) \left(\frac{11}{9907}\right) \left(\frac{13}{9907}\right).$

$\left(\frac{7}{9907}\right) =-\left(\frac{9907}{7}\right) =-\left(\frac{2}{7}\right) =-1$

$\left(\frac{11}{9907}\right) =-\left(\frac{9907}{11}\right) =-\left(\frac{7}{11}\right) =\left(\frac{11}{7}\right) =\left(\frac{4}{7}\right) =1$

$\left(\frac{13}{9907}\right) =\left(\frac{9907}{13}\right) =\left(\frac{1}{13}\right) =1$

$\left(\frac{1001}{9907}\right) =-1$

Using the Jacobi symbol

$\left(\frac{1001}{9907}\right) =\left(\frac{9907}{1001}\right) =\left(\frac{898}{1001}\right) =\left(\frac{2}{1001}\right)\left(\frac{449}{1001}\right) =\left(\frac{449}{1001}\right)$

$=\left(\frac{1001}{449}\right) =\left(\frac{103}{449}\right) =\left(\frac{449}{103}\right) =\left(\frac{37}{103}\right) =\left(\frac{103}{37}\right)$

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

The difference between the two calculations is that when the Legendre symbol is used the "numerator" has to be factored into prime powers before the symbol is flipped. This makes the calculation using the Legendre symbol significantly slower than the one using the Jacobi symbol, as there is no known polynomial-time algorithm for factoring integers.^[4] In fact, this is why Jacobi introduced the symbol.

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 $(\tfrac{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 probabilistic Solovay–Strassen primality test and its refinement the Miller–Rabin primality test.

Notes

^ C.G.J.Jacobi "Uber die Kreisteilung und ihre Anwendung auf die Zahlentheorie", Bericht Ak. Wiss. Berlin (1837) pp 127-136.
^ Almost any textbook on elementary or algebraic number theory, e.g. Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10
^ Calculating $(\tfrac ab)$ requires $O ((log a)(log b))$ operations. See Cohen, pp. 29–31
^ The number field sieve, the fastest known algorithm, requires $O\left(e^{(\ln N)^{1/3}(\ln\ln N)^{2/3}(C+o(1))}\right)$ operations to factor N. See Cohen, p. 495

References

Cohen, Henri (1993), A Course in Computational Algebraic Number Theory, Berlin: Springer, ISBN 3-540-55640-0

Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X

Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66967-4

External links

Calculate Jacobi symbol shows the steps of the calculation.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Jacobi shaddix's home address? Read answer...
	What impact did Karl Gustav Jacob Jacobi have on the world? Read answer...
	What is the Jacobi iteration scheme for a system of linear equations? Read answer...

	Where are Hermann Jacobi pianos?
	How can you contact Sir Derek Jacobi?
	Is Derek Jacobi the voice on Law and Order UK?

Jacobi symbol

Contents