Jacobi symbol

_n∖^m	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
9	0	1	1	0	1	1	0	1	1
11	0	1	−1	1	1	1	−1	−1	−1	1	−1
13	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1
15	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1
17	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1

Jacobi symbol (m/n) for various m (along top) and n (along left side). Only 0 ≤ m < n are shown, since due to rule (2) below any other m can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if m is a quadratic residue modulo a coprime n, then (m/n) = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 row) are quadratic residues. Notice also that when either n or m is a square, all values are nonnegative.

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.

Definition

For any integer $a$ and any positive odd integer $n$ , the Jacobi symbol $\left({\tfrac {a}{n}}\right)$ is defined as the product of the Legendre symbols corresponding to the prime factors of $n$ :

\left({\frac {a}{n}}\right)=\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}},

where $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}$ is the prime factorization of $n$ .

The Legendre symbol $\left({\tfrac {a}{p}}\right)$ is defined for all integers $a$ and all odd primes $p$ by

\left(\frac{a}{p}\right) = \left\{ \begin{array}{rl} 0 & \text{if } a \equiv 0 \pmod{p},\\ 1 & \text{if } a \not\equiv 0\pmod{p} \text{ and for some integer } x\colon\;a\equiv x^2\pmod{p},\\ -1 & \text{if } a \not\equiv 0\pmod{p} \text{ and there is no such } x. \end{array} \right.

Following the normal convention for the empty product, $\left(\tfrac{a}{1}\right) = 1.$

The Legendre and Jacobi symbols are indistinguishable exactly when the lower argument is an odd prime, in which case they have the same value.

Table of values

The following is a table of values of Jacobi symbol $\left({\tfrac {k}{n}}\right)$ with n ≤ 59, k ≤ 30, n odd.

n \ k	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

Properties

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

The Jacobi symbol is defined only when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.

1) If

n

is (an odd) prime, then the Jacobi symbol

\left({\tfrac {a}{n}}\right)

is equal to (and written the same as) the corresponding Legendre symbol.

2) If

a \equiv b \pmod{n}

, then

\left({\tfrac {a}{n}}\right)=\left({\tfrac {b}{n}}\right).

\left({\frac {a}{n}}\right)={\begin{cases}0&{\text{if}}\ \gcd(a,n)\neq 1,\\\pm 1&{\text{if}}\ \gcd(a,n)=1.\end{cases}}

If either the top or bottom argument is fixed, the Jacobi symbol is a completely multiplicative function in the remaining argument:

\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)

, so

\left({\frac {a^{2}}{n}}\right)=1{\text{ or }}0.

\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)

, so

\left({\frac {a}{n^{2}}}\right)=1{\text{ or }}0.

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

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

and its supplements

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

\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:

\left({\tfrac {a}{n}}\right)=-1

then

a

is a quadratic nonresidue modulo

n

a

is a quadratic residue modulo

n

and

\gcd(a,n)=1

, then

\left({\tfrac {a}{n}}\right)=1

But, unlike the Legendre symbol:

\left({\tfrac {a}{n}}\right)=1

then

a

may or may not be a quadratic residue modulo

n

This is because for $a$ to be a quadratic residue modulo $n$ , it has to be a quadratic residue modulo every prime factor of $n$ . However, the Jacobi symbol equals one if, for example, $a$ is a non-residue modulo exactly two of the prime factors of $n$ .

Although the Jacobi symbol cannot be uniformly interpreted in terms of squares and non-squares, it can be uniformly interpreted as the sign of a permutation by Zolotarev's lemma.

The Jacobi symbol $({\tfrac {a}{n}})$ is a Dirichlet character to the modulus $n$ .

Calculating the Jacobi symbol

The above formulas lead to an efficient $O(\log a\log b)$ ^[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).

Reduce the "numerator" modulo the "denominator" using rule 2.
Extract any factors of 2 from the "numerator" using rule 4 and evaluate them using rule 8.
If the "numerator" is $1$ , rules 3 and 4 give a result of $1$ . If the "numerator" and "denominator" are not coprime, rule 3 gives a result of $0$ .
Otherwise, the "numerator" and "denominator" are now odd positive coprime integers, so we can flip the symbol using rule 6, then return to step 1.

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".)

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{2}{29}\right)^3 =-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, and in fact may not even be $-1$ or $1$ . For example,

\left({\frac {19}{45}}\right)=1\,{\text{ and }}\,19^{{(45-1)/2}}\equiv 1{\pmod {45}}.

\left({\frac {8}{21}}\right)=-1\,{\text{ but }}\,8^{{(21-1)/2}}\equiv 1{\pmod {21}}.

\left({\frac {5}{21}}\right)=1\,{\text{ but }}\,5^{{(21-1)/2}}\equiv 16{\pmod {21}}.

So if it is unknown 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 modulo $n$ , then $n$ is composite; if they have the same residue modulo $n$ for many different values of $a$ , then $n$ is "probably prime".

This is the basis for the probabilistic Solovay–Strassen primality test and refinements such as the Baillie-PSW primality test and 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
↑ 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-66957-4

External links

Calculate Jacobi symbol shows the steps of the calculation.

This article is issued from Wikipedia - version of the 11/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.