Jacobi symbol
Introduced by Jacobi in 1837,[1] it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.
For any integer a and any positive odd integer n, the Jacobi symbol (a/n) is defined as the product of the Legendre symbols corresponding to the prime factors of n: where is the prime factorization of n. The Legendre symbol (a/p) is defined for all integers a and all odd primes p by Following the normal convention for the empty product, (a/1) = 1.
[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.
If either the top or bottom argument is fixed, the Jacobi symbol is a completely multiplicative function in the remaining argument: The law of quadratic reciprocity: if m and n are odd positive coprime integers, then and its supplements and
Combining properties 4 and 8 gives: Like the Legendre symbol: But, unlike the Legendre symbol: This is because for a to be a quadratic residue modulo n, it has to be a quadratic residue modulo every prime factor of n. However, the Jacobi symbol equals one if, for example, a is a non-residue modulo exactly two of the prime factors of n. 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 by Zolotarev's lemma.
The Jacobi symbol (a/n) is a Dirichlet character to the modulus n. The above formulas lead to an efficient O(log a log b)[3] algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the gcd of two numbers.
The Legendre symbol (a/p) is only defined for odd primes p. 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".)
If the Euler'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, So if it is unknown whether a number n is prime or composite, we can pick a random number a, calculate the Jacobi symbol (a/n) and compare it with Euler's formula; if they differ modulo n, then n is composite; if they have the same residue modulo n for many different values of a, then n is "probably prime".
As an indirect use, it is possible to use it as an error detection routine during the execution of the Lucas–Lehmer primality test which, even on modern computer hardware, can take weeks to complete when processing Mersenne numbers over
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 of
