Jacobi Symbol Calculator
Calculate the Jacobi symbol (a/n), a generalization of the Legendre symbol used in number theory and primality testing.
The Jacobi symbol (a/n) is defined for any integer a and odd positive integer n
The Jacobi symbol (a/n) is a generalization of the Legendre symbol to composite moduli. It is a multiplicative function that takes values in {-1, 0, 1} and is fundamental in number theory, particularly in primality testing algorithms.
Definition:
- (a/n) = 0 if gcd(a, n) > 1
- (a/n) = (a/p₁)^e₁ × (a/p₂)^e₂ × ... where n = p₁^e₁ × p₂^e₂ × ...
- Each (a/pᵢ) is the Legendre symbol
Key Properties: The Jacobi symbol satisfies multiplicativity: (ab/n) = (a/n)(b/n) and (a/mn) = (a/m)(a/n). It also obeys the law of quadratic reciprocity, which allows efficient computation without factoring.
Quadratic Reciprocity:
For odd positive integers a and n with gcd(a,n) = 1:
(a/n)(n/a) = (-1)^((a-1)(n-1)/4)
This means the product equals -1 only when both a and n are congruent to 3 (mod 4).
Supplement Laws: For odd n: (−1/n) = (−1)^((n−1)/2), which equals 1 if n ≡ 1 (mod 4) and −1 if n ≡ 3 (mod 4). Also, (2/n) = (−1)^((n²−1)/8), which equals 1 if n ≡ ±1 (mod 8) and −1 if n ≡ ±3 (mod 8).
Important Note: Unlike the Legendre symbol, (a/n) = 1 does NOT guarantee that a is a quadratic residue mod n when n is composite. However, (a/n) = −1 does guarantee that a is NOT a quadratic residue mod n.
Applications: The Jacobi symbol is used in the Solovay-Strassen primality test, quadratic sieve factorization, and various cryptographic protocols. It can be computed in O(log² n) time using the reciprocity law, without needing to factor n.
What is the Jacobi symbol used for?
The Jacobi symbol is used in number theory and cryptography, particularly in primality testing algorithms like the Solovay-Strassen test. It generalizes the Legendre symbol to composite moduli and helps determine quadratic residuosity properties of integers.
What is the difference between the Jacobi symbol and Legendre symbol?
The Legendre symbol (a/p) is defined only for odd prime p and tells whether a is a quadratic residue mod p. The Jacobi symbol (a/n) extends this to any odd positive integer n by multiplying Legendre symbols over n's prime factors. However, (a/n) = 1 doesn't guarantee a is a quadratic residue mod n when n is composite.
What does it mean when the Jacobi symbol equals -1?
When the Jacobi symbol (a/n) equals -1, it means a is definitely NOT a quadratic residue modulo n. There is no integer x such that x^2 is congruent to a (mod n). This is useful for ruling out solutions to quadratic congruences.
How is the Jacobi symbol calculated?
The Jacobi symbol is calculated using properties like quadratic reciprocity, without needing to factor n. The algorithm uses: (a/n) = 0 if gcd(a,n) > 1, multiplicativity in both arguments, and the law of quadratic reciprocity to reduce the computation efficiently.