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 determines whether is a quadratic residue modulo a prime the Jacobi symbol is defined for any odd positive integer
The Jacobi symbol was introduced by Carl Gustav Jacob Jacobi in as a computational tool for determining Legendre symbols. Although the Jacobi symbol does not directly indicate whether is a quadratic residue modulo composite 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 and integer with the Legendre symbol is:
By Euler's criterion, When we define
Definition of the Jacobi Symbol
Let be an odd positive integer with prime factorization For any integer the Jacobi symbol is defined as:
where each is the Legendre symbol. For the special case we define for all
The Jacobi symbol takes values in It equals if and only if
Fundamental Properties
The Jacobi symbol satisfies several important properties that make it computationally useful. Let and be odd positive integers and let be integers.
Multiplicativity in the Numerator
This follows directly from the definition and the multiplicativity of the Legendre symbol.
Multiplicativity in the Denominator
This also follows from the definition: the prime factorization of combines the prime factorizations of and
Periodicity
The Jacobi symbol is periodic in the numerator with period
More generally, This allows us to reduce the numerator modulo before computing.
The Value at -1
For any odd positive integer
This generalizes the corresponding result for the Legendre symbol. The proof uses that where the sum is over prime powers in the factorization.
The Value at 2
For any odd positive integer
This is known as the second supplement to quadratic reciprocity. The exponent is always an integer when 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 and with
Equivalently, unless both and in which case
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 similar to the Euclidean algorithm. The key steps are:
Reduce modulo to get .
If return (or if ).
Extract powers of : write where is odd.
Compute using the second supplement.
Apply quadratic reciprocity to swap: .
Repeat with the new arguments.
Relationship to Quadratic Residues
An important caveat: unlike the Legendre symbol, the Jacobi symbol does not imply that is a quadratic residue modulo when is composite.
For example, yet has no solution. This is because is a non-residue mod and mod separately.
However, we do have the following implications:
If then is definitely not a quadratic residue mod
If is prime and then is a quadratic residue mod
Applications
Primality Testing
The Jacobi symbol is central to the Solovay-Strassen primality test. For an odd integer and random with , we check whether:
If is prime, this always holds (by Euler's criterion). If is composite, it fails for at least half of all coprime to . An that fails the test is called an Euler witness to the compositeness of .
Computing Legendre Symbols
To compute the Legendre symbol for a prime we can use the Jacobi symbol algorithm directly (since the Jacobi symbol equals the Legendre symbol when the denominator is prime). This avoids computing via modular exponentiation, which requires multiplications of numbers with 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 modulo a composite The security relies on the difficulty of distinguishing quadratic residues from non-residues with Jacobi symbol .
Generalizations
The Jacobi symbol generalizes to the Kronecker symbol, which extends the definition to allow where 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 - th power residue symbol, we work in a ring containing primitive -th roots of unity. These symbols satisfy higher reciprocity laws discovered by Eisenstein and Kummer.
Summary
The Jacobi symbol extends the Legendre symbol to composite odd moduli. It is defined as the product of Legendre symbols over the prime factorization of
The Jacobi symbol is multiplicative in both arguments, periodic in the numerator, and satisfies the law of quadratic reciprocity:
These properties enable efficient computation without factoring. The supplements give and
Unlike the Legendre symbol, does not guarantee is a quadratic residue when is composite. However, guarantees 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.