Jacobi Symbol

Introduction

The Jacobi symbol is a generalization of the Legendre symbol that extends the theory of quadratic residues from prime moduli to arbitrary odd moduli. While the Legendre symbol (ap) open paren a over p close paren determines whether a a is a quadratic residue modulo a prime p p the Jacobi symbol (an) open paren a over n close paren is defined for any odd positive integer n n

The Jacobi symbol was introduced by Carl Gustav Jacob Jacobi in 1837 1837 as a computational tool for determining Legendre symbols. Although the Jacobi symbol does not directly indicate whether a a is a quadratic residue modulo composite n n it satisfies the law of quadratic reciprocity, making it invaluable for computing Legendre symbols without factoring.

The power of the Jacobi symbol lies in its multiplicative properties. These allow us to reduce computations involving large arguments to simpler cases using only the extended Euclidean algorithm, avoiding the need for prime factorization entirely.

Formal Definition

The Legendre Symbol (Review)

Before defining the Jacobi symbol, we recall the Legendre symbol. For an odd prime p p and integer a a with gcd⁡(a,p)=1 the gcd of open paren a comma p close paren equals 1 the Legendre symbol is:

(ap)={1if a is a quadratic residue mod p−1if a is a quadratic non-residue mod p open paren a over p close paren equals 2 cases Case 1: 1 if a is a quadratic residue mod p Case 2: negative 1 if a is a quadratic non minus residue mod p

By Euler's criterion, (ap)≡a(p−1)/2⁢(mod⁡(p)) open paren a over p close paren is identical to a raised to the open paren p minus 1 close paren divided by 2 power times mod p When gcd⁡(a,p)>1 the gcd of open paren a comma p close paren is greater than 1 we define (ap)=0 open paren a over p close paren equals 0

Definition of the Jacobi Symbol

Let n n be an odd positive integer with prime factorization n=p1e1⁢p2e2⋯pkek n equals p sub 1 raised to the e sub 1 power p sub 2 raised to the e sub 2 power dot dot dot p sub k raised to the e sub k power For any integer a a the Jacobi symbol is defined as:

(an)=(ap1)e1⁢(ap2)e2⋯(apk)ek open paren a over n close paren equals open paren the fraction with numerator a and denominator p sub 1 close paren raised to the e sub 1 power times open paren the fraction with numerator a and denominator p sub 2 close paren raised to the e sub 2 power dot dot dot open paren the fraction with numerator a and denominator p sub k close paren raised to the e sub k power

where each (api) open paren the fraction with numerator a and denominator p sub i close paren is the Legendre symbol. For the special case n=1 n equals 1 we define (a1)=1 open paren a over 1 close paren equals 1 for all a a

The Jacobi symbol (an) open paren a over n close paren takes values in {−1,0,1} the set negative 1 comma 0 comma 1 It equals 0 0 if and only if gcd⁡(a,n)>1 the gcd of open paren a comma n close paren is greater than 1

Fundamental Properties

The Jacobi symbol satisfies several important properties that make it computationally useful. Let m m and n n be odd positive integers and let a,b a comma b be integers.

Multiplicativity in the Numerator

(a⁢bn)=(an)⁢(bn) open paren a b over n close paren equals open paren a over n close paren times open paren b over n close paren

This follows directly from the definition and the multiplicativity of the Legendre symbol.

Multiplicativity in the Denominator

(am⁢n)=(am)⁢(an) open paren a over m n close paren equals open paren a over m close paren times open paren a over n close paren

This also follows from the definition: the prime factorization of m⁢n m n combines the prime factorizations of m m and n n

Periodicity

The Jacobi symbol is periodic in the numerator with period n n

(a+nn)=(an) open paren the fraction with numerator a plus n and denominator n close paren equals open paren a over n close paren

More generally, (an)=(a⁢mod⁡(n)n) open paren a over n close paren equals open paren a mod n over n close paren This allows us to reduce the numerator modulo n n before computing.

The Value at -1

For any odd positive integer n n

(−1n)=(−1)(n−1)/2={1if n≡1⁢(mod⁡(4))−1if n≡3⁢(mod⁡(4)) open paren negative 1 over n close paren equals open paren negative 1 close paren raised to the open paren n minus 1 close paren divided by 2 power equals 2 cases Case 1: 1 if n is identical to 1 times mod 4 Case 2: negative 1 if n is identical to 3 times mod 4

This generalizes the corresponding result for the Legendre symbol. The proof uses that (n−1)/2≡∑i(ei)⁢(pi−1)/2⁢(mod⁡(2)) open paren n minus 1 close paren divided by 2 is identical to the sum over i of open paren e sub i close paren times open paren p sub i minus 1 close paren divided by 2 times mod 2 where the sum is over prime powers in the factorization.

The Value at 2

For any odd positive integer n n

(2n)=(−1)(n2−1)/8={1if n≡±1⁢(mod⁡(8))−1if n≡±3⁢(mod⁡(8)) open paren 2 over n close paren equals open paren negative 1 close paren raised to the exponent open paren n squared minus 1 close paren divided by 8 end exponent equals 2 cases Case 1: 1 if n is identical to plus or minus 1 times mod 8 Case 2: negative 1 if n is identical to plus or minus 3 times mod 8

This is known as the second supplement to quadratic reciprocity. The exponent (n2−1)/8 open paren n squared minus 1 close paren divided by 8 is always an integer when n n is odd.

The Law of Quadratic Reciprocity

The most important property of the Jacobi symbol is that it satisfies the law of quadratic reciprocity. For odd positive integers m m and n n with gcd⁡(m,n)=1 the gcd of open paren m comma n close paren equals 1

(mn)⁢(nm)=(−1)m−12⋅n−12 open paren m over n close paren times open paren n over m close paren equals open paren negative 1 close paren raised to the fraction with numerator m minus 1 and denominator 2 times fraction with numerator n minus 1 and denominator 2 power

Equivalently, (mn)=(nm) open paren m over n close paren equals open paren n over m close paren unless both m≡3⁢(mod⁡(4)) m is identical to 3 times mod 4 and n≡3⁢(mod⁡(4)) n is identical to 3 times mod 4 in which case (mn)=−(nm) open paren m over n close paren equals negative open paren n over m close paren

This remarkable law, first proven by Gauss, allows us to flip the numerator and denominator (with a possible sign change). Combined with the other properties, this enables efficient computation.

The Jacobi Symbol Algorithm

The properties above lead to an efficient algorithm for computing the Jacobi symbol that runs in time O⁢(log2⁡n) O times log squared n similar to the Euclidean algorithm. The key steps are:

  1. Reduce a a modulo n n to get 0≤a<n 0 is less than or equal to a is less than n.

  2. If a=0 a equals 0 return 0 0 (or 1 1 if n=1 n equals 1).

  3. Extract powers of 2 2: write a=2e⋅a′ a equals 2 to the e-th power times a prime where a′ a prime is odd.

  4. Compute (2n)e open paren 2 over n close paren to the e-th power using the second supplement.

  5. Apply quadratic reciprocity to swap: (a′n)=±(na′) open paren the fraction with numerator a prime and denominator n close paren equals plus or minus open paren the fraction with numerator n and denominator a prime close paren.

  6. Repeat with the new arguments.

Relationship to Quadratic Residues

An important caveat: unlike the Legendre symbol, the Jacobi symbol (an)=1 open paren a over n close paren equals 1 does not imply that a a is a quadratic residue modulo n n when n n is composite.

For example, (215)=(23)⁢(25)=(−1)⁢(−1)=1 open paren 2 over 15 close paren equals two thirds times two fifths equals negative 1 times negative 1 equals 1 yet x2≡2⁢(mod⁡(15)) x squared is identical to 2 times mod 15 has no solution. This is because 2 2 is a non-residue mod 3 3 and mod 5 5 separately.

However, we do have the following implications:

If (an)=−1 open paren a over n close paren equals negative 1 then a a is definitely not a quadratic residue mod n n

If n=p n equals p is prime and (ap)=1 open paren a over p close paren equals 1 then a a is a quadratic residue mod p p

Applications

Primality Testing

The Jacobi symbol is central to the Solovay-Strassen primality test. For an odd integer n>1 n is greater than 1 and random a a with 1<a<n 1 is less than a is less than n, we check whether:

a(n−1)/2≡(an)⁢(mod⁡(n)) a raised to the open paren n minus 1 close paren divided by 2 power is identical to open paren a over n close paren times mod n

If n n is prime, this always holds (by Euler's criterion). If n n is composite, it fails for at least half of all a a coprime to n n. An a a that fails the test is called an Euler witness to the compositeness of n n.

Computing Legendre Symbols

To compute the Legendre symbol (ap) open paren a over p close paren for a prime p p we can use the Jacobi symbol algorithm directly (since the Jacobi symbol equals the Legendre symbol when the denominator is prime). This avoids computing a(p−1)/2⁢mod⁡(p) a raised to the open paren p minus 1 close paren divided by 2 power mod p via modular exponentiation, which requires O⁢(log⁡p) O times log p multiplications of numbers with O⁢(log⁡p) O times log p bits.

Cryptography

The Jacobi symbol appears in several cryptographic protocols. In the Goldwasser-Micali encryption scheme, the ciphertext consists of numbers whose Jacobi symbol is 1 1 modulo a composite n=p⁢q n equals p q The security relies on the difficulty of distinguishing quadratic residues from non-residues with Jacobi symbol 1 1.

Generalizations

The Jacobi symbol generalizes to the Kronecker symbol, which extends the definition to allow n=2e⁢m n equals 2 to the e-th power m where m m is odd, and to negative denominators. This further generalization is used in the theory of binary quadratic forms and class field theory.

Higher power residue symbols generalize both the Legendre and Jacobi symbols. For an n n- th power residue symbol, we work in a ring containing primitive n n-th roots of unity. These symbols satisfy higher reciprocity laws discovered by Eisenstein and Kummer.

Summary

The Jacobi symbol (an) open paren a over n close paren extends the Legendre symbol to composite odd moduli. It is defined as the product of Legendre symbols over the prime factorization of n n

(an)=∏iapi open paren a over n close paren equals the product over i of the fraction with numerator a and denominator p sub i

The Jacobi symbol is multiplicative in both arguments, periodic in the numerator, and satisfies the law of quadratic reciprocity:

(mn)⁢(nm)=(−1)m−12⋅n−12 open paren m over n close paren times open paren n over m close paren equals open paren negative 1 close paren raised to the fraction with numerator m minus 1 and denominator 2 times fraction with numerator n minus 1 and denominator 2 power

These properties enable efficient computation without factoring. The supplements give (−1n)=(−1)(n−1)/2 open paren negative 1 over n close paren equals open paren negative 1 close paren raised to the open paren n minus 1 close paren divided by 2 power and (2n)=(−1)(n2−1)/8 open paren 2 over n close paren equals open paren negative 1 close paren raised to the exponent open paren n squared minus 1 close paren divided by 8 end exponent

Unlike the Legendre symbol, (an)=1 open paren a over n close paren equals 1 does not guarantee a a is a quadratic residue when n n is composite. However, (an)=−1 open paren a over n close paren equals negative 1 guarantees a a is not a quadratic residue.

The Jacobi symbol is used in primality testing (Solovay-Strassen), computing Legendre symbols efficiently, and cryptographic protocols. It generalizes to the Kronecker symbol and higher power residue symbols, connecting elementary number theory to class field theory.