Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Jacobi symbol

From Wikipedia, the free encyclopedia
Generalization of the Legendre symbol in number theory
Carl Gustav Jacob Jacobi who introduced the symbol.
k
n
012345678910111213141516
11
301−1
501−1−11
7011−11−1−1
9011011011
1101−1111−1−1−11−1
1301−111−1−1−1−111−11
150110100−1100−10−1−1
17011−11−1−1−111−1−1−11−111

Jacobi symbol(⁠k/n⁠) for variousk (along top) andn (along left side). Only0 ≤k <n are shown, since due to rule (2) below any otherk can be reduced modulon.Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and ifk is a quadratic residue modulo a coprimen, then(⁠k/n⁠) = 1, but not all entries with a Jacobi symbol of 1 (see then = 9 andn = 15 rows) are quadratic residues. Notice also that when eithern ork is a square, all values are nonnegative.

TheJacobi symbol is a generalization of theLegendre symbol. Introduced byJacobi in 1837,[1] it is of theoretical interest inmodular arithmetic and other branches ofnumber theory, but its main use is incomputational number theory, especiallyprimality testing andinteger factorization; these in turn are important incryptography.

Definition

[edit]

For any integera and any positive odd integern, the Jacobi symbol(⁠a/n⁠) is defined as the product of theLegendre symbols corresponding to the prime factors ofn:

(an):=(ap1)α1(ap2)α2⋯(apk)αk,{\displaystyle \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=p1α1p2α2⋯pkαk{\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}

is the prime factorization ofn.

The Legendre symbol(⁠a/p⁠) is defined for all integersa and all odd primesp by

(ap):={0if a≡0(modp),1if a≢0(modp) and for some integer x:a≡x2(modp),−1if a≢0(modp) and there is no such x.{\displaystyle \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,(⁠a/1⁠) = 1.

When the lower argument is an odd prime, the Jacobi symbol is equal to the Legendre symbol.

Table of values

[edit]

The following is a table of values of Jacobi symbol(⁠k/n⁠) withn ≤ 59,k ≤ 30,n odd.

k
n
123456789101112131415161718192021222324252627282930
1111111111111111111111111111111
31−101−101−101−101−101−101−101−101−101−10
51−1−1101−1−1101−1−1101−1−1101−1−1101−1−110
711−11−1−1011−11−1−1011−11−1−1011−11−1−1011
9110110110110110110110110110110
111−1111−1−1−11−101−1111−1−1−11−101−1111−1−1−1
131−111−1−1−1−111−1101−111−1−1−1−111−1101−111
15110100−1100−10−1−10110100−1100−10−1−10
1711−11−1−1−111−1−1−11−111011−11−1−1−111−1−1−11
191−1−11111−11−11−1−1−1−111−101−1−11111−11−11
211−101100−10−1−10−100110−1101−101100−10
231111−11−111−1−111−1−11−11−1−1−1−101111−11−1
25111101111011110111101111011110
271−101−101−101−101−101−101−101−101−101−10
291−1−11111−11−1−1−11−1−11−1−1−11−11111−1−1101
3111−111−11111−1−1−11−11−1111−1−1−1−11−1−11−1−1
331101−10−110−100−1−10110−1−100−101−10−110
351−1110−10−1101110011−1−100−1−1−10−11010
371−111−1−11−11111−1−1−11−1−1−1−11−1−1−11111−11
39110110−1101100−101−10−1101−10100−1−10
4111−111−1−1111−1−1−1−1−11−11−111−11−11−1−1−1−1−1
431−1−11−11−1−1111−111111−1−1−11−1111−1−1−1−1−1
451−10100−1−10010−1101−10100−1−10010−110
471111−11111−1−11−11−1111−1−11−1−111−111−1−1
49111111011111101111110111111011
511−10110−1−10−110110100110−1101−10−110
531−1−11−111−1111−11−1111−1−1−1−1−1−111−1−111−1
5511−110−111100−1110111−10−10−1−101−11−10
571101−10110−1−10−1101−100−10−1−101−10110
591−1111−11−11−1−11−1−1111−11111−1−111111−1

Properties

[edit]

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. Ifn is (an odd) prime, then the Jacobi symbol(⁠a/n⁠) is equal to (and written the same as) the corresponding Legendre symbol.
2. Ifa ≡b  (modn), then(an)=(bn)=(a±m⋅nn){\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)}
3.(an)={0if gcd(a,n)≠1,±1if gcd(a,n)=1.{\displaystyle \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 acompletely multiplicative function in the remaining argument:

4.(abn)=(an)(bn),so (a2n)=(an)2=1 or 0.{\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{so }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}
5.(amn)=(am)(an),so (an2)=(an)2=1 or 0.{\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{so }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}

Thelaw of quadratic reciprocity: ifm andn are odd positive coprime integers, then

6.(mn)(nm)=(−1)m−12⋅n−12={1if n≡1(mod4) or m≡1(mod4),−1if n≡m≡3(mod4){\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\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

7.(−1n)=(−1)n−12={1if n≡1(mod4),−1if n≡3(mod4),{\displaystyle \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}}},

and(1n)=(n1)=1{\displaystyle \left({\frac {1}{n}}\right)=\left({\frac {n}{1}}\right)=1}

8.(2n)=(−1)n2−18={1if n≡1,7(mod8),−1if n≡3,5(mod8).{\displaystyle \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}}}

Combining properties 4 and 8 gives:

9.(2an)=(2n)(an)={(an)if n≡1,7(mod8),−(an)if n≡3,5(mod8).{\displaystyle \left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 1,7{\pmod {8}},\\{-\left({\frac {a}{n}}\right)}&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}

Like the Legendre symbol:

  • If(⁠a/n⁠) = −1 thena is a quadratic nonresidue modulon.

But, unlike the Legendre symbol:

If(⁠a/n⁠) = 1 thena may or may not be a quadratic residue modulon.

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

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 byZolotarev's lemma.

The Jacobi symbol(⁠a/n⁠) is aDirichlet character to the modulusn.

Calculating the Jacobi symbol

[edit]

The above formulas lead to an efficientO(loga logb)[3]algorithm for calculating the Jacobi symbol, analogous to theEuclidean algorithm for finding the gcd of two numbers. (This should not be surprising in light of rule 2.)

  1. Reduce the "numerator" modulo the "denominator" using rule 2.
  2. Extract any even "numerator" using rule 9.
  3. 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.
  4. 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.

In addition to the codes below, Riesel[4] has it inPascal.

Implementation inLua

[edit]
functionjacobi(n,k)assert(k>0andk%2==1)n=n%kt=1whilen~=0dowhilen%2==0don=n/2r=k%8ifr==3orr==5thent=-tendendn,k=k,nifn%4==3andk%4==3thent=-tendn=n%kendifk==1thenreturntelsereturn0endend

Implementation inC++

[edit]
// a/n is represented as (a,n)intjacobi(inta,intn){assert(n>0&&n%2==1);// Step 1a=(a%n+n)%n;// Handle (a < 0)// Step 3intt=0;// XOR of bits 1 and 2 determines sign of return valuewhile(a!=0){// Step 2while(a%4==0)a/=4;if(a%2==0){t^=n;// Could be "^= n & 6"; we only care about bits 1 and 2a/=2;}// Step 4t^=a&n&2;// Flip sign if a % 4 == n % 4 == 3intr=n%a;n=a;a=r;}if(n!=1)return0;elseif((t^(t>>1))&2)return-1;elsereturn1;}

Example of calculations

[edit]

The Legendre symbol(⁠a/p⁠) is only defined for odd primesp. It obeys the same rules as the Jacobi symbol (i.e., reciprocity and the supplementary formulas for(⁠−1/p⁠) and(⁠2/p⁠) and multiplicativity of the "numerator".)

Problem: Given that 9907 is prime, calculate(⁠1001/9907⁠).

Using the Legendre symbol

[edit]
(10019907)=(79907)(119907)(139907).(79907)=−(99077)=−(27)=−1.(119907)=−(990711)=−(711)=(117)=(47)=1.(139907)=(990713)=(113)=1.(10019907)=−1.{\displaystyle {\begin{aligned}\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.\end{aligned}}}

Using the Jacobi symbol

[edit]
(10019907)=(99071001)=(8981001)=(21001)(4491001)=(4491001)=(1001449)=(103449)=(449103)=(37103)=(10337)=(2937)=(3729)=(829)=(229)3=−1.{\displaystyle {\begin{aligned}\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.\end{aligned}}}

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.[5] In fact, this is why Jacobi introduced the symbol.

Primality testing

[edit]

There is another way the Jacobi and Legendre symbols differ. If theEuler's 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,

(1945)=1 and 1945−12≡1(mod45).(821)=−1 but 821−12≡1(mod21).(521)=1 but 521−12≡16(mod21).{\displaystyle {\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}}

So if it is unknown whether a numbern is prime or composite, we can pick a random numbera, calculate the Jacobi symbol(⁠a/n⁠) and compare it with Euler's formula; if they differ modulon, thenn is composite; if they have the same residue modulon for many different values ofa, thenn is "probably prime".

This is the basis for the probabilisticSolovay–Strassen primality test and refinements such as theBaillie–PSW primality test and theMiller–Rabin primality test.

As an indirect use, it is possible to use it as an error detection routine during the execution of theLucas–Lehmer primality test which, even on modern computer hardware, can take weeks to complete when processingMersenne numbers over2136,279,841−1{\displaystyle {\begin{aligned}2^{136,279,841}-1\end{aligned}}} (the largest known Mersenne prime as of October 2024). In nominal cases, the Jacobi symbol:

(si−2Mp)=−1i≠0{\displaystyle {\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}}

This also holds for the final residuesp−2{\displaystyle {\begin{aligned}s_{p-2}\end{aligned}}} and hence can be used as a verification of probable validity. However, if an error occurs in the hardware, there is a 50% chance that the result will become 0 or 1 instead, and won't change with subsequent terms ofs{\displaystyle {\begin{aligned}s\end{aligned}}} (unless another error occurs and changes it back to -1).

See also

[edit]

Notes

[edit]
  1. ^Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie".Bericht Ak. Wiss. Berlin:127–136.
  2. ^Ireland & Rosen pp. 56–57 or Lemmermeyer p. 10
  3. ^Cohen, pp. 29–31
  4. ^p. 285
  5. ^Thenumber field sieve, the fastest known algorithm, requires
    O(e(ln⁡N)13(ln⁡ln⁡N)23(C+o(1))){\displaystyle O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)}
    operations to factorn. See Cohen, p. 495

References

[edit]

External links

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Jacobi_symbol&oldid=1262775442"
Category:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp