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 (a/p) determines whether a is a quadratic residue modulo a prime p the Jacobi symbol (a/n) is defined for any odd positive integer n

The Jacobi symbol was introduced by Carl Gustav Jacob Jacobi in 1837 as a computational tool for determining Legendre symbols. Although the Jacobi symbol does not directly indicate whether a is a quadratic residue modulo composite 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 and integer a with gcd(a,p)=1 the Legendre symbol is:

(a/p)={[1,if *a* is a quadratic residue mod *p],[−1,if *a* is a quadratic non-residue mod *p])

By Euler's criterion, (a/p)≡a((p−1)/2)*(mod(p)) When gcd(a,p)>1 we define (a/p)=0

Definition of the Jacobi Symbol

Let n be an odd positive integer with prime factorization n=(p_1)(e_1)*(p_2)(e_2)⋯(p_k)(e_k) For any integer a the Jacobi symbol is defined as:

(a/n)=(a/(p_1))(e_1)*(a/(p_2))(e_2)⋯(a/(p_k))(e_k)

where each (a/(p_i)) is the Legendre symbol. For the special case n=1 we define (a/1)=1 for all a

The Jacobi symbol (a/n) takes values in {−1,0,1} It equals 0 if and only if gcd(a,n)>1

Fundamental Properties

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

Multiplicativity in the Numerator

((a*b)/n)=(a/n)*(b/n)

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

Multiplicativity in the Denominator

(a/(m*n))=(a/m)*(a/n)

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

Periodicity

The Jacobi symbol is periodic in the numerator with period n

((a+n)/n)=(a/n)

More generally, (a/n)=((a*mod(n))/n) This allows us to reduce the numerator modulo n before computing.

The Value at -1

For any odd positive integer n

((−1)/n)=(−1)((n−1)/2)={[1,if *n≡1*(mod(4))],[−1,if *n≡3*(mod(4))])

This generalizes the corresponding result for the Legendre symbol. The proof uses that (n−1)/2≡(∑_i^)((e_i))*((p_i)−1)/2*(mod(2)) where the sum is over prime powers in the factorization.

The Value at 2

For any odd positive integer n

(2/n)=(−1)((n2−1)/8)={[1,if *n≡±1*(mod(8))],[−1,if *n≡±3*(mod(8))])

This is known as the second supplement to quadratic reciprocity. The exponent (n2−1)/8 is always an integer when 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 and n with gcd(m,n)=1

(m/n)*(n/m)=(−1)((m−1)/2⋅(n−1)/2)

Equivalently, (m/n)=(n/m) unless both m≡3*(mod(4)) and n≡3*(mod(4)) in which case (m/n)=−(n/m)

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*((log_)2(n)) similar to the Euclidean algorithm. The key steps are:

1. Reduce a modulo n to get 0≤a<n.

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

3. Extract powers of 2: write a=2⋅(a^′) where (a^′) is odd.

4. Compute (2/n)e using the second supplement.

5. Apply quadratic reciprocity to swap: ((a^′)/n)=±(n/(a^′)).

6. Repeat with the new arguments.

Relationship to Quadratic Residues

An important caveat: unlike the Legendre symbol, the Jacobi symbol (a/n)=1 does not imply that a is a quadratic residue modulo n when n is composite.

For example, (2/15)=(2/3)*(2/5)=(−1)*(−1)=1 yet x2≡2*(mod(15)) has no solution. This is because 2 is a non-residue mod 3 and mod 5 separately.

However, we do have the following implications:

If (a/n)=−1 then a is definitely not a quadratic residue mod n

If n=p is prime and (a/p)=1 then a is a quadratic residue mod p

Applications

Primality Testing

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

a((n−1)/2)≡(a/n)*(mod(n))

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

Computing Legendre Symbols

To compute the Legendre symbol (a/p) for a prime 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) via modular exponentiation, which requires O*((log_)(p)) multiplications of numbers with O*((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 modulo a composite n=p*q The security relies on the difficulty of distinguishing quadratic residues from non-residues with Jacobi symbol 1.

Generalizations

The Jacobi symbol generalizes to the Kronecker symbol, which extends the definition to allow n=2*m where 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- th power residue symbol, we work in a ring containing primitive n-th roots of unity. These symbols satisfy higher reciprocity laws discovered by Eisenstein and Kummer.

Summary

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

(a/n)=(∏_i^)(a/(p_i))

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

(m/n)*(n/m)=(−1)((m−1)/2⋅(n−1)/2)

These properties enable efficient computation without factoring. The supplements give ((−1)/n)=(−1)((n−1)/2) and (2/n)=(−1)((n2−1)/8)

Unlike the Legendre symbol, (a/n)=1 does not guarantee a is a quadratic residue when n is composite. However, (a/n)=−1 guarantees 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.