68 Jacobi Symbol

The Jacobi symbol extends the Legendre symbol to the case where the “denominator” is an arbitrary odd positive number n.

Let n be an odd positive integer with prime factorization ∏ _i=1^kp_i^e_i. We define the Jacobi symbol by

(1)

where the symbol on the left is the Jacobi symbol, and the symbol on the right is the Legendre symbol. (By convention, this product is 1 when k = 0, so = 1.) Clearly, when n = p is an odd prime, the Jacobi symbol and Legendre symbols agree, so the Jacobi symbol is a true extension of our earlier notion.

What does the Jacobi symbol mean when n is not prime? If = -1 then a is definitely not a quadratic residue modulo n, but if = 1, a might or might not be a quadratic residue. Consider the important case of n = pq for p, q distinct odd primes. Then

so there are two cases that result in = 1: either = = +1 or = = -1. In the first case, a is a quadratic residue modulo both p and q, so a is a quadratic residue modulo n. In the second case, a is not a quadratic residue modulo either p or q, so it is not a quadratic residue modulo n, either. Such numbers a are sometimes called “pseudo-squares” since they have Jacobi symbol 1 but are not quadratic residues.

69 Identities Involving the Jacobi Symbol

The Jacobi symbol is easily computed if the factorization of n is known using Equation 1 above and Theorem 1 of lecture 12, section 67. Similarly, gcd(u,v) is easily computed given the factorizations of u and v, without resort to the Euclidean algorithm. The remarkable fact about the Euclidean algorithm is that it lets us compute gcd(u,v) efficiently even without knowing the factors of u and v. A similar algorithm allows the Jacobi symbol to be computed efficiently without knowing the factorization of a or n.

The algorithm is based on identities satisfied by the Jacobi symbol:

1. = 1; = 0 for n1;
2. = 1 if n ≡±1 (mod 8); = -1 if n ≡±3 (mod 8);
3. = if a₁ ≡ a₂ (mod n);
4. = ;
5. = - if a ≡ n ≡ 3 (mod 4).
6. = if a ≡ 1 (mod 4) or (a ≡ 3 (mod 4) and n ≡ 1 (mod 4));

There are many ways to turn these identities into an algorithm. Below is a straightforward recursive approach. Slightly more efficient iterative implementations are also possible.

70 Solovay-Strassen Test of Compositeness

Recall that a test of compositeness for n is a set of predicates {τ_a(n)}_aZ*n such that if τ(n) succeeds (is true), then n is composite. The Solovay-Strassen Test is the set of predicates {ν_a(n)}_aZ*n, where

If n is prime, the test always fails by Theorem 1 of lecture 12, section 67. Equivalently, if some ν_a(n) succeeds, then n must be composite. Hence, the test is a valid- test of compositeness.

Let b = a^(n-1)∕2, so b² ≡ a^n-1. There are two possible reasons why the test might succeed. One possibility is that a^n-1 ⁄≡ 1 (mod n) in which case b ⁄≡±1 (mod n). This is just the Fermat test ζ_a(n) from section 51 of lecture notes 10. A second possibility is that a^n-1 ≡ 1 (mod n) but nevertheless, b ⁄≡ (mod n). In this case, b is a square root of 1 (mod n), but it might have the opposite sign from , or it might not even be ±1 since 1 has additional square roots when n is composite. Strassen and Solovay show that at the probability that ν_a(n) succeeds for a randomly-chosen a Z*_n is at least 1∕2 when n is composite.¹

71 Miller-Rabin Test of Compositeness

The Miller-Rabin Test is more complicated to describe than the Solovay-Strassen Test, but the probability of error (that is, the probability that it fails when n is composite) seems to be lower than for Solovay-Strassen, so that the same degree of confidence can be achieved using fewer iterations of the test. This makes it faster when incorporated into a primality-testing algorithm. It is also closely related to the algorithm presented in section 55.3 (lecture notes 10) for factoring an RSA modulus given the encryption and decryption keys.

71.1 The test

The test μ_a(n) is based on computing a sequence b₀,b₁,…,b_k of integers in Z*_n. If n is prime, this sequence ends in 1, and the last non-1 element, if any, is n- 1 (≡-1 (mod n)). If the observed sequence is not of this form, then n is composite, and the Miller-Rabin Test succeeds. Otherwise, the test fails.

The sequence is computed as follows:

1. Write n- 1 = 2^km, where m is an odd positive integer. Computationally, k is the number of 0’s at the right (low-order) end of the binary expansion of n, and m is the number that results from n when the k low-order 0’s are removed.
2. Let b₀ = a^m mod n.
3. For i = 1,2,…,k, let b_i = (b_i-1)² mod n.

An easy inductive proof shows that b_i = a^2im mod n for all i, 0 ≤ i ≤ k. In particular, b_k ≡ a^2km = a^n-1 (mod n).

71.2 Validity

To see that the test is valid, we must show that μ_a(p) fails for all a Z*_p when p is prime. By Euler’s theorem² , a^p-1 ≡ 1 (mod p), so we see that b_k = 1. Since 1 has only two square roots, 1 and -1, modulo p, and b_i-1 is a square root of b_i modulo p, the last non-1 element in the sequence (if any) must be -1 mod p. This is exactly the condition for which the Miller-Rabin test fails. Hence, it fails whenever n is prime, so if it succeeds, n is indeed composite.

71.3 Accuracy

How likely is it to succeed when n is composite? It succeeds whenever a^n-1 ⁄≡ 1 (mod n), so it succeeds whenever the Fermat test ζ_a(n) would succeed. (See section 51 of lecture notes 10.) But even when a^n-1 ≡ 1 (mod n) and the Fermat test fails, the Miller-Rabin test will succeed if the last non-1 element in the sequence of b’s is one of the square roots of 1 other than ±1. It can be proved that μ_a(n) succeeds for at least 3∕4 of the possible values of a. Empirically, the test almost always succeeds when n is composite, and one has to work to find a such that μ_a(n) fails.

71.4 Example

For example, take n = 561 = 3 ⋅ 11 ⋅ 17. This number is interesting because it is the first Carmichael number. A Carmichael number is an odd composite number n that satisfies a^n-1 ≡ 1 (mod n) for all a Z*_n. (See http://mathworld.wolfram.com/CarmichaelNumber.html.) These are the numbers that I have been calling “pseudoprimes”. Let’s go through the steps of computing μ₃₇(561).

We begin by finding m and k. 561 in binary is 1000110001 (a palindrome!). Then n - 1 = 560 = (1000110000)₂, so k = 4 and m = (100011)₂ = 35. We compute b₀ = a^m = 37³⁵ mod 561 = 265 with the help of the computer. We now compute the sequence of b’s, also with the help of the computer. The results are shown in the table below:

This sequence ends in 1, but the last non-1 element b₃ ⁄≡-1 (mod 561), so the test μ₃₇(561) succeeds. In fact, the test succeeds for every a Z*₅₆₁ except for a = 1,103,256,460,511. For each of those values, b₀ = a^m ≡ 1 (mod 561).

71.5 Optimization

In practice, one only wants to compute as many of the b’s as necessary to determine whether or not the test succeeds. In particular, one can stop after computing b_i if b_i ≡±1 (mod n). If b_i ≡-1 (mod n) and i < k, the test fails. If b_i ≡ 1 (mod n) and i ≥ 1, the test succeeds. This is because we know in this case that b_i-1 ⁄≡-1 (mod n), for if it were, the algorithm would have stopped after computing b_i-1.