A 22-million digit prime number

The first digits of 2 to 77,232,917 minus 1

The digits in the above picture are the first digits of the newest largest prime number known to humankind. It was discovered on December 26, 2017. The number is equaled to 2 raided to 77,232,917 less 1, making this a Mersenne prime. It has over 22 million digits (23,249,425 to be precise). If we were to write 5 digits per inch, the digits would cover a stretch of highway of over 73 miles in length!

We already wrote about this newly discovered largest prime in two places (here and here).

For more on Mersenne primes, see here or Google the Internet.

\text{ }

Dan Ma math

Daniel Ma mathematics

Dan Ma prime numbers

\copyright 2018 – Dan Ma

Mersenne Prime

A Mersenne number is an integer that is one less than a power of 2, i.e. it is of the form 2^n-1 where n is a positive integer. A Mersenne prime number (or a Mersenne prime) is a Mersenne number that happens to be a prime number. This post is a brief discussion on Mersenne prime.

Because Mersenne numbers are exponential, they increase very rapidly. The first several Mersenne numbers 2^n-1 starting with n = 2.

    3, 7, 15, 31, 63, 127, 255, 511, 1,023, 2,047, 4,095, 8,191, 16,383, 32,767, ……

It is clear from these examples that not all Mersenne numbers are prime (e.g. 15 and 63). In the above list, the numbers in red are prime and the ones in blue are composite. Note that the ones with composite exponent n are composite: 15 (n = 4), 63 (n = 6), 255 (n = 8), 511 (n = 9) …. This is no coincidence.

Whenever n is composite, the Mersenne number 2^n-1 is also composite.

The fact follows from the following identity.

    \displaystyle \begin{aligned} 2^{ab}-1&=(2^a-1) \ (1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) \\&=(2^b-1) \ (1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b})  \end{aligned}

Thus if we are interested in finding numbers 2^n-1 that are prime, we must start with an exponent n that is prime. For ease of discussion, define M_p=2^p-1 and assume that p is prime.

Mersenne primes have a long history. Long before the computer age, people had been doing primality testing on Mersenne numbers. The first four Mersenne primes M_p, for p = 2, 3, 5, and 7, were known in antiquity. The next Mersenne prime M_{13} was discovered before 1461. People at that time thought that M_p is prime whenever p is prime. In 1536, Hudalricus Regius found that M_{11}=2^{11}-1=2047=23 \times 89. In 1603, Pietro Cataldi showed that M_p is prime for p = 17 and 19.

The name of Mersenne prime was due to the connection with the French monk Marin Mersenne. In his 1644 book Cognita Physico-Mathematica, Mersenne stated that M_p is prime when p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Some of these claims were later determined to be wrong. His list also missed some correct Mersenne primes. From then on, his name was attached to this particular type of prime numbers.

The next discovery of a Mersenne prime (after Pietro Cataldi), M_{31}, was made by Leonhard Euler in 1772. The one found after Euler’s, M_{127}, was made by Edouard Lucas in 1876. There were three more Mersenne primes discovered before the computer age – M_{61} in 1883 by Ivan Pervushin, M_{89} and M_{107} by R. E. Powers in 1911 and 1914, respectively.

In the pre-computer age, there were long stretches of time in between discoveries of Mersenne primes. For example, it took almost 200 years after Pietro Cataldi for the next Mersenne prime to emerge (discovered by Euler). There were about 100 years in between Euler’s discovery and Lucas’ discovery.

Another important contribution made by Lucas is a test that he developed to test Mersenne numbers to see if they are prime. The test was originally developed in 1856 and later improved by him in 1878. It was further improved by Derrick Henry Lehmer in the 1930s. The test is now known as the Lucas-Lehmer test.

Lucas-Lehmer Test. Define a sequence of positive integers S_0, S_1, S_2, S_3, \cdots such that S_0=4 and S_j=S_{j-1}^2-2 where j \ge 1. Suppose that p \ge 3. Then M_p=2^p-1 is a Mersenne prime if and only if M_p divides S_{p-2}.

To perform the test, start with S_0=4 and recursively calculate S_j=S_{j-1}^2-2 until S_{p-2} is obtained. Then perform the division of S_{p-2} by M_p. If S_{p-2} is divisible by M_p, then M_p is prime. If S_{p-2} is not divisible by M_p, then M_p is composite. It is interesting that when M_p is found to be composite in this manner, the compositeness of M_p is established without finding any prime factors of M_p.

The computer discoveries of Mersenne primes began in 1952 by Raphael Robinson. The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search (GIMPS) to discover large primes. GIMPS is a distributed computing project on the Internet for finding large prime numbers.

As of the writing of this post (May 25, 2017), a total of 49 Mersenne primes had been discovered. The latest one is M_{74207281}, with over 22 million digits, which was found in January 2016.

Despite of the computation advance, there are still many fundamental questions that are still not known about Mersenne primes. For example, how many Mersenne primes are there? It is not even known whether the set of Mersenne primes is finite or infinite. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite.

Because of the Lucas-Lehmer test, whenever someone finds a new largest prime number, it is usually a Mersenne prime. So every few years or so, Mersenne prime is on the news for the reason of being discovered. For up-to-date information or to learn more about basic facts, go to the Mersenne prime website and the Wikipedia entry on Mersenne primes.

____________________________________________________________________________
\copyright 2017 – Dan Ma

Fermat numbers

Two previous posts (here and here) present an alternative proof that there are infinitely many prime numbers using the Fermat numbers. Specifically, the proof is accomplished by pointing out that the prime factors of the Fermat numbers form an infinite set. This post takes a look at Fermat numbers in more details.

A Fermat number is of the form \displaystyle F_n=2^{2^n}+1 where n=0,1,2,3,\cdots. The numbers grow very rapidly since each Fermat number is obtained by raising 2 to a power of 2. The first several terms are 3, 5, 17, 257, 65,537, 4,294,967,297. They are named after the French mathematicians Pierre de Fermat (1601-1665). He demonstrated that the first 5 Fermat numbers F_0, F_1, F_2, F_3, F_4 are prime and conjectured that all Fermat numbers are prime. In 1732, Euler provided a counterexample to the conjecture by showing that

    \displaystyle F_5=2^{2^5}+1=2^{32}+1=4294967297=641 \times 6700417

Any Fermat number that is also a prime number is said to be a Fermat prime. Other than F_0, F_1, F_2, F_3, F_4, no additional Fermat primes have been discovered.

Euler likely did not factor F_5 by trial division. Euler discovered that the prime factors of Fermat numbers have a specific form. This discovery led to 641 being a factor of F_5. We discussed this result and other basic facts of Fermat numbers as well as the Pepin’s test, which is a primality testing algorithm that works on Fermat numbers as well as the Pepin’s test.

____________________________________________________________________________

Basic Results

One interesting fact is that Fermat numbers can be defined (or generated) recursively. Any Fermat number can be derived by taking the product of all the preceding Fermat numbers plus 2. Another basic fact is that the Fermat numbers are pairwise relatively prime, i.e. any two Fermat numbers have no common factor other 1. These two facts are stated in Theorem 1 and Theorem 2 below, which are proved in this previous post.

Theorem 1
For n \ge 1, we have the following results:

  • F_n=(F_{n-1}-1)^2+1.
  • F_n=F_0 \times \cdots \times F_{n-1}+2.

Theorem 2
For i \ne j, F_i and F_j are relatively prime.

A corollary of Theorem 1 and Theorem 2 is that there are infinitely many prime numbers. Another corollary of Theorem 1 is that all Fermat numbers, except for the first two, end in the digit of 7.

Corollary 3
There are infinitely many prime numbers.

Corollary 4
For n \ge 2, the last digit of F_n is 7.

To see Corollary 3, if F_n is prime, then let p_n=F_n. If not, let p_n be the smallest prime factor of F_n. By Theorem 2, the prime numbers p_n are pairwise relatively prime, hence pairwise distinct.

To see Corollary 4, note that F_n \equiv 2 \ (\text{mod} \ F_j) for j <n (this follows from Theorem 1). In particular, F_n \equiv 2 \ (\text{mod} \ 5). Equivalently, F_n-2=5k for some integer k. Since all F_n are odd, k is odd. Thus k=2j+1 for some j and F_n-2=10j+5. Subtracting 5 on both sides gives F_n-7=10j. This means that F_n \equiv 7 \ (\text{mod} \ 10).

____________________________________________________________________________

The Prime Factors of Fermat Numbers

The Fermat numbers F_0 to F_{4} are prime. No additional Fermat primes had been identified since the time of Fermat. The Fermat numbers F_5 to F_{11} have been completely factored. With a few exceptions, the numbers F_{12} to F_{43} are partially factored. The exceptions: F_{20} and F_{24} are shown to be composite (with no known factors) while F_{33} to F_{35} and F_{40} and F_{41} have unknown status. Beyond F_{43}, there is a long list of partially factored F_n for 43<n \le 3329780. For the most up to date factoring status of Fermat numbers, see here.

There are no known Fermat primes other than the first five (F_0 to F_4). For the Fermat numbers beyond F_4, there are only finite number of them that are known to be composite. There are interesting and natural questions that can be raised about Fermat numbers. Is there another Fermat prime? Are there infinitely many Fermat primes (Eisenstein 1844)? Are there infinitely many composite Fermat numbers? Is F_n composite for all n>4?

In this section, we consider some basic facts about prime factors of Fermat numbers. What if we relax the definition of Fermat numbers by considering the numbers 2^m+1 where m is a nonnegative integer that does not necessarily have to be a power of 2? Can 2^m+1 be a prime number? It turns out that if we want to look at 2^m+1 that are prime numbers, we have to restrict our attention to Fermat numbers. This is stated more formally in Theorem 5.

Theorem 5
If 2^m+1 is a prime number, then m is a power of 2.

Proof of Theorem 5
Let 2^m+1 be a prime number. Let m=b \times 2^w where w \ge 0 and b \ge 1 is odd. Now 2^m+1=(2^{2^w})^b+1. To make it easy to see the argument, let A=2^{2^w} and B=-1. Note that (2^{2^w})^b+1=A^b-B^b. Furthermore A-B=2^{2^w}+1 divides A^b-B^b. This means that 2^{2^w}+1 is a factor of 2^m+1. Since 2^m+1 is prime, 2^{2^w}+1=2^m+1. That implies that b=1. As a result, m=2^w. \square

Theorem 5 is a useful result. It tells us that 2 raised to odd power plus 1 can never be prime. For example, 2^{11}+1 is not prime. Without any calculation, we known that 2^w+1 is composite if w = 2,305,843,009,213,693,953. On the other hand, 2 raised to any even power is not prime as long as the even power is not a power of 2. For example, 2^{20}+1 is not prime. Just to be clear, when m is a power of 2, it does not mean 2^m+1 is a prime. The Fermat number F_5 is a counterexample. The property in Theorem 5 is a necessary and not a sufficient condition. So far we only know of five example of prime 2^m+1 where m is a power of 2. We next consider the prime factors of a Fermat number.

Theorem 6 (Euler-Lucas)
For any integer n \ge 2, any prime factor p of F_n=2^{2^n}+1 is of the form p=k \times 2^{n+2}+1 for some integer k.

Proof of Theorem 6
Let p be a prime factor of F_n. From the definition of Fermat numbers, observe that 2^{2^n} \equiv -1 \ (\text{mod} \ p). Squaring both sides gives 2^{2^{n+1}} \equiv 1 \ (\text{mod} \ p). We claim that the order of the element 2 modulo p is 2^{n+1}. Suppose the order of the element 2 modulo p is 2^{j} where j<n+1, equivalently j \le n. Then 2^{2^{j}} \equiv 1 \ (\text{mod} \ p) and 2^{2^{n}} \equiv 1 \ (\text{mod} \ p), a contradiction. Thus the claim is true.

Furthermore, the order of 2 modulo p would divide \phi(p)=p-1 where \phi(\cdot) is the Euler's phi function (see corollary 5 here). Thus 2^{n+1} would divide p-1 or p=j \times 2^{n+1}+1 for some j.

The result in the preceding paragraph is the result of Euler. Now to the improvement by Lucas. Since n \ge 2, p \equiv 1 \ (\text{mod} \ 8). By the second supplement to the law of quadratic reciprocity (Theorem 8 found here), the element 2 is a quadratic residue modulo p. This means that r^2 \equiv 2 \ (\text{mod} \ p) for some integer r. Raise both sides to 2^{n+1} gives r^{2^{n+2}} \equiv 2^{2^{n+1}} \equiv 1 \ (\text{mod} \ p). We claim that the order of the element r modulo p is 2^{n+2}. Suppose the order of the element r modulo p is 2^{j} where j<n+2, or equivalently j \le n+1. Then r^{2^{j}} \equiv 1 \ (\text{mod} \ p) and r^{2^{n+1}} \equiv 1 \ (\text{mod} \ p). Note that r^{2^{n+1}} \equiv (r^2)^{2^n} \equiv 2^{2^n} \equiv 1 \ (\text{mod} \ p). This contradicts the congruence 2^{2^n} \equiv -1 \ (\text{mod} \ p) observed earlier. The claim is established.

As a result of the fact that the order of the element r modulo p is 2^{n+2}, 2^{n+2} divides \phi(p)=p-1. Equivalently, p=k \times 2^{n+2}+1 for some k. \square

When a Fermat number is determined to be composite (e.g. via Theorem 7 below), Theorem 6 indicates that its prime factors are of a certain form. For the Fermat number F_5, the factor 641 can be derived as follows. First, note the following two relations.

    641=5 \times 2^7+1

    641=5^4+2^4

From the first fact, 5 \cdot 2^7 \equiv -1 \ (\text{mod} \ 641). Raising both sides to 4 gives 5^4 \cdot 2^{28} \equiv 1 \ (\text{mod} \ 641). From the second fact, 5^4 \equiv -2^4 \ (\text{mod} \ 641). Combining the two congruences gives -2^4 \cdot 2^{28} \equiv - 2^{32} \equiv 1 \ (\text{mod} \ 641), which means that 641 divides F_5=2^{32}+1.

____________________________________________________________________________

Primality Testing of Fermat Numbers

Because the Fermat numbers grow so rapidly, factoring large Fermat numbers is a challenge. However, there is a polynomial-time algorithm that determines the primality of a Fermat number (see Theorem 7 below). But even this test is limited because of the rapid growth of Fermat numbers.

Theorem 7 (Pepin’s Test)
For n \ge 1, the Fermat number F_n=2^{2^n}+1 is a prime number if and only if \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n).

Proof of Theorem 7
Suppose that F_n=2^{2^n}+1 is prime where n \ge 1. We claim that the number 3 is a quadratic nonresidue modulo F_n. Once this is established, the congruence \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n) would follow by appealing to Euler’s criterion (see Theorem 1 here). To see the claim, note that

    \displaystyle \biggl( \frac{3}{F_n} \biggr)=\biggl( \frac{F_n}{3} \biggr)=\biggl( \frac{2}{3} \biggr)=-1

The above symbols are Legendre symbols since F_n is a prime number. The first symbol can be flipped without changing the sign since F_n \equiv 1 \ (\text{mod} \ 4). This is according to the law of quadratic reciprocity (see Theorem 6 here). It follows from the first bullet point in Theorem 1 that F_n \equiv 2 \ (\text{mod} \ 3) for all n \ge 1. Thus the second Legendre symbol above is the same as the third symbol. Lastly, 2 is a quadratic nonresidue modulo 3. Thus the third Legendre symbol above equals -1. By Euler’s criterion, this means that the congruence \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n) holds.

The other direction uses Lucas’ primality test, which is a test that proves the primality for any integer p such that the factorization of p-1 is completely known. Fermat numbers fit the requirement since F_n-1 is a power of 2. For the statement and proof of Lucas’ primality test, see Theorem 1 here. To show the other direction, suppose that \displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n) where n \ge 1. Clearly, \displaystyle 3^{F_n-1} \equiv 1 \ (\text{mod} \ F_n). By Lucas’ primality test, F_n is prime. \square

The number 3 is the base used in the Pepin’s test as stated in Theorem 7. Other bases can be used, e.g. 5. The following is the Pepin’s test using 5 as the base.

Theorem 8 (Pepin’s Test)
For n \ge 2, the Fermat number F_n=2^{2^n}+1 is a prime number if and only if \displaystyle 5^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n).

The proof for Theorem 8 works similarly. If F_n is prime, it can be shown that 5 is a quadratic nonresidue modulo F_n.

To determine whether a given Fermat number F_n is prime, simply compute the congruence \displaystyle 3^{\frac{F_n-1}{2}} \ (\text{mod} \ F_n). If the result is -1, then F_n being tested is a prime number. If the congruence is not -1, then F_n is composite. Note that the results from Pepin’s test can only tell whether the given Fermat number is prime or composite. If the test result says composite, it does not indicate what the factors are. The following shows the test results for F_4 to F_{10}.

    \displaystyle 3^{\frac{F_4-1}{2}} \equiv 65536 \equiv -1 \ (\text{mod} \ F_4)

    \displaystyle 3^{\frac{F_5-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_5)
    where T = 10,324,303
    and F_5 = 4,294,967,297

    \displaystyle 3^{\frac{F_6-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_6)
    where T = 11,860,219,800,640,380,469
    and F_6 = 18,446,744,073,709,551,617

    \displaystyle 3^{\frac{F_7-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_7)
    where T = 110,780,954,395,540,516,579,111,562,860,048,860,420
    and F_7 = 340,282,366,920,938,463,463,374,607,431,768,211,457

    \displaystyle 3^{\frac{F_8-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_8)
    where T = 005,864,545,399,742,183,862,578,018,016,183,410,025,465,491,904,722,516,203,269,973,267,547,486,512,819
    and F_8 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,937

    \displaystyle 3^{\frac{F_9-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_9)
    where T =
    03,487,842,192,292,834,160,828,677,804,926,452,873,307,656,935,026,758,634,839,951,511,167,913,561,583
    764,893,191,647,059,299,508,808,058,740,314,515,096,456,032,583,684,082,248,245,196,170,211,101,691,254
    and F_9 =
    13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073
    546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,097

    \displaystyle 3^{\frac{F_{10}-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_{10})
    where T =
    387,619,810,475,491,122,179,739,047,140,959,275,426,443,598,784,645,243,238,994,975,074,552,393,367
    151,669,166,056,942,068,042,567,969,383,237,719,504,044,259,561,712,002,215,552,049,762,078,784,904
    229,994,959,756,192,565,270,005,114,398,071,628,663,530,167,797,163,602,701,669,757,405,752,156,537
    276,004,764,083,329,886,967,333,347,443,567,401,688,754,399,623,980,380,190,579,140,626,590,345,932,472,472
    and F_9 =
    179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805
    500,963,132,708,477,322,407,536,021,120,113,879,871,393,357,658,789,768,814,416,622,492,847,430,639
    474,124,377,767,893,424,865,485,276,302,219,601,246,094,119,453,082,952,085,005,768,838,150,682,342
    462,881,473,913,110,540,827,237,163,350,510,684,586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,217

____________________________________________________________________________

Remarks

The above calculations can be performed on a calculator that can handle modular exponentiation or be programmed in a computer. The above calculations point to the reality that it is much easier to determine the status of primality/compositeness of a number than the factorization. For example, the compositeness of F_8 was known in 1909 but the factors were not found until 1980.

The modular exponentiations displayed above, 3 raised to (F_n-1)/2, can be accomplished by performing a series of squaring and multiplications. This approach is called the square-and-multiply approach or the fast powering algorithm. In this algorithm, the binary expansion of the exponent is used to convert the exponentiation into a series of squarings and multiplications. See here for a description of the fast powering algorithm. See here for a simpler description. One interesting point that can be made about the calculation for the Pepin’s test is that the exponent is a power of 2. As a result, there is only one non-zero bit in the binary expansion (the highest bit). So the square-and-multiply only consists of squarings. In any programming attempt, the “multiply” part can be skipped.

The algorithm described in Theorem 7 (Pepin’s test) is a polynomial-time algorithm assuming that the input F_n is written in binary or decimal numbers. It seems that one can simply apply Pepin’s test on larger and larger Fermat numbers to gain more insight on the open questions on Fermat numbers. However, Pepin’s test, though efficient, is also a limited test. Because the exponent in the test is a power of 2 that increases rapidly, the test reaches a computational limit rather quickly.

Let’s look at the computational limit through F_{33}, which is the least Fermat number with unknown status. It has 2,585,827,973 decimal digits. In applying Pepin’s test, the exponent would be 2^{2^{33}-1}, which has 2^{33} = 8,589,934,593 many bits in the binary expansion (that’s the number of squarings required in the fast powering algorithm, over 8.5 billions)! Thus applying Pepin’s test (in conjunction with the fast powering algorithm) on the larger Fermat numbers is no small feat. The following comments from [1] give a good perspective on the Pepin’s test.

    The first Fermat number of unresolved character is thus F_{33}. By conventional machinery and Pepin test, the resolution of F_{33} would take us well beyond the next ice age! So the need for new algorithms is as strong as can be for future work on giant Fermat numbers.

According to the comments made in Wikipedia, Pepin’s test had been used 8 times in resolving the prime/composite status of Fermat numbers. To tackle large Fermat numbers, technology improvement (hardware, software and algorithm) will be needed. Thus progress may take decades or more.

There is one interesting question about Pepin’s test. What are all the possible bases that can be used in this test? Are there other bases beside 3 and 5? This is discussed in in another blog post.

____________________________________________________________________________

Reference

  1. Crandall R., Pomerance C,Prime Numbers, A Computational Perspective, Second Edition, Springer, New York, 2005

____________________________________________________________________________
\copyright \ 2016 \text{ by Dan Ma}

Tweaking a proof of the infinitude of primes

This blog presents two proofs of the infinitude of primes. The first one is the standard proof that is due to Euclid (around 300 BC). The second one is due to Christian Goldbach (from a letter to Leonhard Euler in 1730). This post attempts to generalize the second one. The goal is to capture the essence of the proof and in the process gains a better perspective. Reading the second proof is not a prerequisite. The reader is welcome to compare the argument here with the previous proof to appreciate the economy that is in the tweaked proof.

____________________________________________________________________________

The Tweak

The existence of the following sequence will imply that there are infinitely many prime numbers.

    There is a sequence of positive odd integers x_0,x_1,x_3, \cdots such that

    • x_0 < x_1 < x_3 < \cdots,
    • any two elements of the sequence are relatively prime, i.e. for i \ne j, the terms x_i and x_j have no common divisor other than 1.

If such a sequence exists, we can infer an infinite sequence of prime numbers. Note that each term x_j is a product of distinct primes. Let p_j be the smallest prime factor of x_j. The prime numbers p_j must be distinct since the elements in the sequence x_0,x_1,x_3, \cdots are pairwise relatively prime.

How do we know if such a sequence exists? It can be defined recursively. Let x_0<x_1 be any odd positive integers that are relatively prime. For example, x_0=3 and x_1=5. Another example: x_0=21 and x_1=55. Then for each n>1, let x_n=x_0 \times x_1 \times \cdots \times x_{n-1}+2. Clearly the sequence is increasing. To see that any two terms of the sequence are relatively prime, let j<n and let d be a common divisor of x_j and x_n. Since d divides x_j, it is clear that d divides x_0 \times x_1 \times \cdots \times x_{n-1}. This means that d divides x_n-x_0 \times x_1 \times \cdots \times x_{n-1}=2. With d being odd and d dividing 2, it must be that d=1.

The proof in the previous post essentially uses the above argument with the first two terms fixed at x_0=3 and x_1=5. With these two initial choices, it can be shown that the sequence x_0,x_1,x_3, \cdots consists of the Fermat numbers. It is nice to know that the resulting sequence consists of the Fermat numbers. However, for proving that primes are infinite, the fact about Fermat numbers is immaterial. For example, if the initial two terms are x_0=21 and x_1=55, the same argument will still lead to an infinite sequence of prime numbers. Using Fermat numbers is one way to derive the sequence in question. Sometimes a broader picture picture can be obscured by being too specific in the argument.

____________________________________________________________________________

An Equivalent Statement

The above argument for the infinitude of primes points to the fact that the existence of an infinite sequence of prime numbers is reduced to the existence of a sequence as described in the above argument. We have the following theorem.

Theorem
The following two statements are equivalent.

  • There exists a sequence of positive odd integers x_0,x_1,x_3, \cdots such that x_0 < x_1 < x_3 < \cdots and such that any two terms of the sequence are relatively prime.
  • There are infinitely many prime numbers.

It is clear that if there are infinitely many primes, the sequence x_0,x_1,x_3, \cdots can simply be made the primes. So one direction is obvious. The other direction is proved by the above argument.

The theorem essentially says that the “infinity” of primes is identical to the “infinity” of numbers that are pairwise relatively prime. Of course, the purpose of discussing the latter is to give an argument that there are infinitely many primes.

____________________________________________________________________________
\copyright \ 2016 \text{ by Dan Ma}

Solving quadratic congruences with odd prime moduli

The goal of this post is to show how to solve the quadratic congruence equation

    x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where p is an odd prime and a is an integer that is relatively prime to p. When equation (1) has a solution, the number a is said to be a quadratic residue modulo p. Any solution of equation (1) is called a square root of a modulo p. When the equation has no solutions, the number a is said to be a quadratic nonresidue modulo p. For both theoretical and practical reasons, it is important to solve quadratic congruence equation (1) (or to find square roots modulo an odd prime). This post expands on the previous post called Solving Quadratic Congruences.

____________________________________________________________________________

Background

If the modulus p is small (prime or composite), then it is easy to solve equation (1). Simply square each element in the set \left\{1,2,\cdots,p-1 \right\} modulo p and look for the value a. We need a systematic method only when the modulus is large to the point that checking for solutions by squaring one number at a time cannot be done in a reasonable amount of time using modern supercomputers.

The moduli discussed here are prime numbers p. The case p=2 is easy to deal with. Thus in solving equations described in (1), the focus is on odd primes p and on integers a that are relatively prime to p.

In solving the quadratic congruence equation (1), for that matter any other type of equations, three natural questions arise: given an equation of the form in (1), how do I know if it has a solution? If it has a solution, how many solution does it have? How do I compute a solution of one exists? It turns out that for quadratic congruence equations with odd prime moduli as described in (1), there are clear and definite answers for all three questions.

There is an effective algorithm for checking whether a is a quadratic residue modulo p. The algorithm is to evaluate the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr) (see these two previous posts: Legendre symbol and Jacobi symbol). As for the second question (the number of solutions), the equation (1) either has no solutions or has exactly two solutions (see the post called Solving Quadratic Congruences). Thus for an odd prime p, exactly half of the elements in the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} are quadratic residues modulo p. In other words, modulo an odd prime p, there are (p-1)/2 many quadratic residues and (p-1)/2 many quadratic nonresidues. To answer the third question, we discuss algorithms that can be used to solve quadratic congruences with odd prime moduli.

Any odd prime is congruent to either 1 or 3 modulo 4. For odd prime p \equiv 3 \ (\text{mod} \ 4), there is an explicit formula that gives the solutions to equation (1). For odd prime p \equiv 1 \ (\text{mod} \ 4), no explicit formula exists. For the case of p \equiv 1 \ (\text{mod} \ 4), we demonstrate how to use the Tonelli-Shanks algorithm to iteratively find the solutions. We describe the algorithm and show how it works with some examples. We also present a proof of why the algorithm works.

The Tonelli-Shanks algorithm was invented in 1972 by Dan Shanks. He called it RESSOL (RESidues SOLver). The algorithm is very similar to one described much earlier by Tonelli, hence the name Tonelli-Shanks algorithm.

____________________________________________________________________________

Odd primes congruent to 3 modulo 4

Let’s take care of the easy case first, i.e. p \equiv 3 \ (\text{mod} \ 4). In this case, the solutions to equation (1) are given by \pm R where

    \displaystyle R \equiv a^{\frac{p+1}{4}} \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

To see that the R gives a solution to the equation (1), consider the following derivation:

    \displaystyle \begin{aligned} R^2&\equiv (a^{\frac{p+1}{4}})^2 \\&\equiv a^{\frac{p+1}{2}} \\&\equiv a \cdot a^{\frac{p-1}{2}} \\&\equiv a \cdot \biggl(\frac{a}{p}\biggr) \\&\equiv a \cdot 1  \\&\equiv a \ (\text{mod} \ p) \end{aligned}

On the surface, it appears that the above derivation works for all primes. Note that the exponent (p+1)/4 must be an integer. The assumption p \equiv 3 \ (\text{mod} \ 4) makes it an integer. Using Euler’s Criterion, the quantity \displaystyle a^{\frac{p-1}{2}} is replaced by the Lengendre symbol, which is a 1 since a is a quadratic residue modulo p.

As a quick example, let’s solve the equation x^2 \equiv 19 \ (\text{mod} \ 431). The prime 431 is congruent to 3 modulo 4. The number 19 is a quadratic residue modulo 431. One solution is given by 19^{432/4} \equiv 19^{108} \equiv 197 \ (\text{mod} \ 431). The other solution is given by 234 (= 431-197).

____________________________________________________________________________

Odd primes congruent to 1 modulo 4

The focus of the remainder of the post is on using the Tonelli-Shanks algorithm to solve the quadratic equation (1). We describe the algorithm in the next section and demonstrate with examples. To follow along the algorithm and the examples, it would be helpful to have a calculator (or a software package) that can handle modular exponentiation and the evaluation of Legendre symbol and Jacobi symbol. The algorithm also requires the finding of a quadratic nonresidue modulo the odd prime p. Obviously, we need to check that the number a is a quadratic residue modulo p. This can be done by evaluating the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr).

____________________________________________________________________________

Tonelli-Shanks Algorithm

Objective: to solve the equation x^2 \equiv a \ (\text{mod} \ p) where p is an odd prime satisfying p \equiv 1 \ (\text{mod} \ 4) and a is a quadratic residue modulo p, i.e. the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr)=1.

Steps:

  1. Factor out the largest power of 2 from the even integer p-1, i.e. obtain p-1=2^{S} \cdot Q where Q is odd.
  2. Find a positive integer y that is a quadratic nonresidue modulo p, i.e. find y such that \displaystyle  \biggl(\frac{y}{p}\biggr)=-1.
  3. Calculate the following four quantities:
    • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
    • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
    • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
    • \displaystyle E=S
  4. Loop
    1. If \displaystyle t \equiv 1 \ (\text{mod} \ p), then the algorithm stops and output R and p-R, the two solutions of the equation. If \displaystyle t \not \equiv 1 \ (\text{mod} \ p), then perform the following two steps.
    2. Find the least i such that 0<i<E and such that \displaystyle t^{2^i} \equiv 1 \ (\text{mod} \ p).
    3. Calculate \displaystyle b \equiv c^{2^{E-i-1}} \ (\text{mod} \ p) and replace the quantities R, c, t and E as follows:
      • \displaystyle R \equiv Rb \ (\text{mod} \ p)
      • \displaystyle c \equiv b^2 \ (\text{mod} \ p)
      • \displaystyle t \equiv b^2 \cdot t \ (\text{mod} \ p)
      • \displaystyle E=i

      Go back to Step A.

The initial value of \displaystyle R \equiv a^{\frac{Q+1}{2}} is an initial estimate of the solution to the equation. The rest of the algorithm is to repeatedly refine this estimate to reach a solution. Note that Step 4-B is to determine the order of the number t. Each time a new value of t is calculated, the order of the new t is smaller than the order of the previous t. The goal is to reach a t of order 1, which means that the number t itself would be \equiv 1, at which point the estimate R becomes a solution. Let’s consider some examples.

____________________________________________________________________________

Examples

Example 1
Solve the equation x^2 \equiv 381 \ (\text{mod} \ 593).

The following shows the steps in carrying out the Tonelli-Shanks algorithm.

Step 1. S=4 and Q=37 since 592 = 16 x 37.

Step 2. y=3 is a quadratic nonresidue modulo 593.

Step 3. Calculate the following four quantities:

  • \displaystyle R \equiv 381^{\frac{37+1}{2}} \equiv 381^{19} \equiv 218 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 3^{37} \equiv 384 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 381^{37} \equiv 201 \ (\text{mod} \ 593)
  • \displaystyle E=4

_______________________________________
The above t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. In other words, repeatedly square t until reaching the value of 1. The result is i=3. Let b \equiv c^{2^{E-i-1}} \equiv 384^{2^{4-3-1}} \equiv 384 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 218 \cdot 384 \equiv 99 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 384^{2} \equiv 392 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 201 \cdot 392 \equiv 516 \ (\text{mod} \ 593)
  • \displaystyle E=3

_______________________________________
The last t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. The result is i=2. Note that the order of t goes from 2^3 previously to 2^2.

Let b \equiv c^{2^{E-i-1}} \equiv 392^{2^{3-2-1}} \equiv 392 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 99 \cdot 392 \equiv 263 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 392^{2} \equiv 77 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 516 \cdot 77 \equiv 1 \ (\text{mod} \ 593)
  • \displaystyle E=2

Now we reach t \equiv 1. The solutions to the equations are: 263 and 330 (=593 – 263). \square

Example 2
Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 2795830049 and a= 2262876953.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=5 and Q= 87369689.

Step 2. y=3 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2075434035
  • \displaystyle c \equiv 3^{Q} \equiv 268289123
  • \displaystyle t \equiv a^{Q} \equiv 2666735226
  • \displaystyle E=5

The above t is obviously not 1. So we need to perform the loop several times.

_______________________________________
Iteration 1

  • i=4, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{5-4-1}} \equiv c \equiv 268289123
  • \displaystyle R_1 \equiv R \cdot b \equiv 2438491248
  • \displaystyle c_1 \equiv b^2 \equiv 717416975
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 2569006270
  • \displaystyle E_1=4

_______________________________________
Iteration 2

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{4-2-1}} \equiv c_1^2 \equiv 17652213
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 2519954933
  • \displaystyle c_2 \equiv b^2 \equiv 2569006270
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 2795830048
  • \displaystyle E_2=2

_______________________________________
Iteration 3

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{2-1-1}} \equiv c_2 \equiv 2569006270
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv  1147516973
  • \displaystyle c_3 \equiv b^2 \equiv 2795830048
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 1
  • \displaystyle E_3=1

_______________________________________
Solutions

  • \displaystyle R \equiv 1147516973
  • \displaystyle p-R \equiv 1648313076

____________________________________________________________________________

Why the algorithm works

To prove that the algorithm produces the solutions to the given equation, we need the following lemma.

Lemma
Suppose that both g and h are relatively prime to an odd prime number p. Suppose that the order of g modulo p is 2^j with j being a positive integer. Suppose that the order of h modulo p is also 2^j. Then the order of g \cdot h modulo p is 2^k where k<j.

Proof
Since the order of g is 2^j, \displaystyle y=g^{2^{j-1}} \not \equiv 1 \ (\text{mod} \ p). Note that \displaystyle y^2 \equiv g^{2^{j}} \equiv 1 \ (\text{mod} \ p). Then it must be that y \equiv -1 \ (\text{mod} \ p) since the equation x^2 \equiv 1 \ (\text{mod} \ p) has only two solutions. By a similar argument, h^{2^{j-1}} \equiv -1 \ (\text{mod} \ p). Consider the following:

    \displaystyle (gh)^{2^{j-1}} \equiv g^{2^{j-1}} \cdot h^{2^{j-1}} \equiv (-1) (-1) \equiv 1 \ (\text{mod} \ p)

This means that the order of g \cdot h divides 2^{j-1}. Thus the order of g \cdot h modulo p must be 2^{k} for some k \le j-1 < j. \square

Proof of Tonelli-Shanks algorithm
Since p is an odd prime, we set p-1=Q \cdot 2^{S} where Q is odd. We also select a positive integer y that is a quadratic nonresidue modulo p. To start the calculation, obtain the following four quantities:

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
  • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
  • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
  • \displaystyle E=S

The quantity R is an initial estimate of the desired solution since

    \displaystyle R^2 \equiv a^{Q+1} \equiv a \cdot a^Q \equiv a \cdot t \ (\text{mod} \ p)

If t \equiv 1 \ (\text{mod} \ p), then R would be a solution and the algorithm stops. So assume that t \not \equiv 1 \ (\text{mod} \ p). Then we begin a loop to fine tune R until reaching a step with t \equiv 1 \ (\text{mod} \ p).

To make sense of the loop in the algorithm, consider the quantity c and the quantity t. First of all, the integer c has order 2^S modulo p, as shown below.

    \displaystyle c^{2^S} \equiv (y^{Q})^{2^S} \equiv y^{p-1} \equiv (y^{\frac{p-1}{2}})^2 \equiv (-1)^2 \equiv 1 \ (\text{mod} \ p)

    \displaystyle c^{2^{S-1}} \equiv (y^{Q})^{2^{S-1}} \equiv y^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)

Furthermore, the order of t modulo p is less or equal to 2^S since \displaystyle t^{2^S} \equiv 1 \ (\text{mod} \ p) as shown below.

    \displaystyle t^{2^S} \equiv (a^{Q})^{2^S} \equiv a^{p-1} \equiv (a^{\frac{p-1}{2}})^2 \equiv (1)^2 \equiv 1 \ (\text{mod} \ p)

Let 2^{S_1} be the order of t where S_1 \le S. Now begin the calculation for the first iteration of the loop. First, calculate \displaystyle b_1 \equiv c^{2^{E-S_1-1}} \ (\text{mod} \ p).

  • \displaystyle R_1 \equiv R \cdot b_1 \ (\text{mod} \ p)
  • \displaystyle c_1 \equiv b_1^2 \ (\text{mod} \ p)
  • \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p)
  • \displaystyle E_1=S_1

One important point to make is that the order of c_1 modulo p is the same as the order of t, which is 2^{S_1}. The following shows why.

    \displaystyle c_1^{2^{S_1}} \equiv (b_1^2)^{2^{S_1}} \equiv b_1^{2^{S_1+1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1+1}} \equiv c^{2^S} \equiv 1 \ (\text{mod} \ p)

    \displaystyle c_1^{2^{S_1-1}} \equiv (b_1^2)^{2^{S_1-1}} \equiv b_1^{2^{S_1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1}} \equiv c^{2^{S-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p) is 2^{S_2} for some S_2<S_1. Note that

    \displaystyle R_1^2 \equiv R^2 \cdot b_1^2 \equiv a \cdot t \cdot c_1 \equiv a \cdot t_1 \ (\text{mod} \ p)

In light of the above, if \displaystyle t_1 \equiv 1 \ (\text{mod} \ p), then R_1 is a solution and the algorithm stops. Even if \displaystyle t_1 \not \equiv 1 \ (\text{mod} \ p), there is progress since the order of t_1 is less than the previous t with 2^{S_2}<2^{S_1}. Repeat the loop to obtain t_2, \cdots, t_k with the order of t_k being 2^{S_{k+1}}=1 where S_{k+1}=0. When the order of t_k is 1, t_k=1. When the modulus is a prime, there is only one element with order 1, namely the element 1. Then the quantity R_j is a solution to the given equation.

To further illustrate, we perform one more iteration of the loop. Let \displaystyle b_2 \equiv c_1^{2^{E_1-S_2-1}} \ (\text{mod} \ p). Calculate the following four quantities:

  • \displaystyle R_2 \equiv R_1 \cdot b_2 \ (\text{mod} \ p)
  • \displaystyle c_2 \equiv b_2^2 \ (\text{mod} \ p)
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p)
  • \displaystyle E_2=S_2

Similar to the previous step, the order of c_2 is the same as the order of t_1 as shown below:

    \displaystyle C_2^{2^{S_2}} \equiv (b_2^2)^{2^{S_2}} \equiv b_2^{2^{S_2+1}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2+1}} \equiv c_1^{2^{E_1}} \equiv c_1^{2^{S_1}} \equiv 1 \ (\text{mod} \ p)

    \displaystyle C_2^{2^{S_2-1}} \equiv (b_2^2)^{2^{S_2-1}} \equiv b_2^{2^{S_2}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2}} \equiv c_1^{2^{E_1-1}} \equiv c_1^{2^{S_1-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p) is 2^{S_3} for some S_3<S_2. Note the following:

    \displaystyle R_2^2 \equiv R_1^2 \cdot b_2^2 \equiv a \cdot t_1 \cdot c_2 \equiv a \cdot t_2 \ (\text{mod} \ p)

Now we reach the same decision point. If t_2 \equiv 1, then R_2 is a solution and the algorithm stops. Even if t_2 \not \equiv 1, the order of t_2 is smaller than previously. Continue to execute the loop until the step where the order of t_k is 1. \square

____________________________________________________________________________

Comments

The Tonelli-Shanks algorithm works correctly (as the proof indicated) and works efficiently (as the examples show). The speed of the algorithm is a function of the inputs. The inputs to the Tonelli-Shanks algorithm are the odd prime p and the quadratic residue a modulo p. The two inputs are translated to the three quantities m, k and S where m is the number of digits in the binary representation of the odd prime p, k is the number of ones in the binary representation of p and S is the largest power of 2 in the factor of p-1. These three numbers determine the amount of calculations. According to this source, the average number of modular multiplications required by the Tonelli-Shanks algorithm is:

    \displaystyle 2m+2k+\frac{S(S-1)}{4}+\frac{1}{2^{S-1}}-9

Another consideration is the selection of y, a quadratic nonresidue modulo p, which can be found by checking random selections from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\}. Since half the elements in the set are quadratic residues, it takes on average two random selections from this set (hence two computations of the Legendre symbol). One way to see this is that the number of Bernoulli trials until the first success has a geometric distribution. The probability of success in each trial is 0.5. Then the mean of the geometric distribution is 1/0.5 = 2.

Overall, the Tonelli-Shanks algorithm works efficiently in solving the quadratic congruence equation (1). Along with the explicit formula (2) that handles the case of odd prime congruent to 3 modulo 4, the quadratic congruence equations are completely and efficiently solved. As a result, it is not possible to hide secrets using quadratic congruence equations with odd prime moduli. If a message is embedded as a solution of such equation, then it can be easily recovered using the Tonelli-Shanks algorithm or the explicit formula (2). On the other hand, the equation

    x^2 \equiv a \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

is difficult to solve where the modulus n is the product of two large primes p and q. In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of n is known, equation (3) is solvable and the Tonelli-Shanks algorithm along with the Chinese remainder theorem play a crucial role.

____________________________________________________________________________

Another example

Example 3
This is a slightly larger example than the ones given earlier. Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 3825123056546413057 and a= 1347234680313589343.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=9 and Q= 7470943469817213.

Step 2. y=5 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2098778229504385555
  • \displaystyle c \equiv 5^{Q} \equiv 945046778698092498
  • \displaystyle t \equiv a^{Q} \equiv 3356211917617579979
  • \displaystyle E=9

The above t is obviously not 1. So we need to perform the loops several times.

_______________________________________
Iteration 1

  • i=8, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{9-8-1}} \equiv c \equiv 945046778698092498
  • \displaystyle R_1 \equiv R \cdot b \equiv 852974818860733646
  • \displaystyle c_1 \equiv b^2 \equiv 777225398785777536
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 3130593564544117824
  • \displaystyle E_1=8

_______________________________________
Iteration 2

  • i=7, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{8-7-1}} \equiv c_1 \equiv 777225398785777536
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 1437578878907258220
  • \displaystyle c_2 \equiv b^2 \equiv 872612747799733789
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 3053369905528253481
  • \displaystyle E_2=7

_______________________________________
Iteration 3

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{7-2-1}} \equiv c_2^{2^5} \equiv 2409792470045159888
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv 1136125891705727966
  • \displaystyle c_3 \equiv b^2 \equiv 3053369905528253481
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 3825123056546413056
  • \displaystyle E_3=2

_______________________________________
Iteration 4

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_3^{2^{E_3-i-1}} \equiv c_3^{2^{2-1-1}} \equiv c_3^{2^0} \equiv c_3 \equiv 3053369905528253481
  • \displaystyle R_4 \equiv R_3 \cdot b \equiv  3727993796269536942
  • \displaystyle c_4 \equiv b^2 \equiv 3825123056546413056
  • \displaystyle t_4 \equiv c_4 \cdot t_3 \equiv 1
  • \displaystyle E_4=1

_______________________________________
Solutions

  • \displaystyle R \equiv 3727993796269536942
  • \displaystyle p-R \equiv 97129260276876115

____________________________________________________________________________

Exercises

We close with some exercises. Use Tonelli-Shanks algorithm to solve the equation x^2 \equiv a \ (\text{mod} \ p) for each of the following choices of a and p.

  1. p=193 and a = 67
  2. p=569 and a = 367
  3. p=34369 and a = 19170
  4. p=50753 and a = 12957
  5. p=97241 and a = 47861
  6. p=2773676993 and a = 1342865413

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Solutions are:

  1. 35 and 158
  2. 103 and 466
  3. 19136 and 15233
  4. 30781 and 19972
  5. 45733 and 51508
  6. 1056882643 and 1716794350

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

The Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. In this post, we define the Jacobi symbol and discuss some of its important properties. The Legendre symbol (coupled with the law of reciprocity) is a useful tool in determining whether a number is a quadratic residue modulo an odd prime. However, the Legendre symbol is also restrictive since the bottom argument must be a prime. The Jacobi symbol generalizes the Legendre symbol and in many cases is easier to evaluate than the Legendre symbol. This is demonstrated in several examples.

____________________________________________________________________________

Defining The Jacobi Symbol

The Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr) where the bottom argument is always an odd prime and the top argument can be any integer. When a is an integer that is relatively prime to the odd prime p, the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr) carries information on whether the integer a is quadratic residue modulo p. The following gives the definition of the Legendre symbol.

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\           1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

The Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr) has the same look as the Legendre symbol. The top argument can be any integer. The bottom argument is an odd positive integer. If the odd positive integer n>1 has the prime factorization n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}, the Jacobi symbol is defined as follows:

    \displaystyle  \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{p_1}\biggr)^{e_1} \times \biggl(\frac{a}{p_2}\biggr)^{e_2} \times \cdots \times \biggl(\frac{a}{p_t}\biggr)^{e_t}

For convenience, we define \displaystyle  \biggl(\frac{a}{1}\biggr)=1. A slightly different, but equivalent, definition is that whenever the odd integer n>1 has the prime factorization n=q_1 \times q_2 \times \cdots \times q_k (the prime numbers q_j are not necessarily distinct), the symbol \displaystyle  \biggl(\frac{a}{n}\biggr) is defined as follows:

    \displaystyle  \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{q_1}\biggr) \times \biggl(\frac{a}{q_2}\biggr) \times \cdots \times \biggl(\frac{a}{q_k}\biggr)

The Jacobi symbol is defined using the Legendre symbol according to the prime factorization of the bottom argument.

____________________________________________________________________________

Properties of The Jacobi Symbol

Now that the Jacobi symbol has been defined based on the Legendre symbol, there are two natural questions.

  • Does the value of \displaystyle  \biggl(\frac{a}{n}\biggr)= \pm 1 indicates that a is a quadratic residue or nonresidue modulo n?
  • The Legendre symbol follows a set of rules (e.g. the law of quadratic reciprocity) that make the Legendre symbol a versatile tool. Does the Jacobi symbol follow these rules? Conceptually, evaluating the Jacobi symbol requires factoring the bottom argument of the symbol. On the surface, this appears to be a limitation. However, if the Jacobi symbol follows the rules for the Legendre symbol including the law of quadratic reciprocity, it will be just as easy to evaluate the Jacobi symbol.

For the first question, the following is true: If a is a quadratic residue modulo n, then \displaystyle  \biggl(\frac{a}{n}\biggr)=1. The contrapositive of this statement is that if \displaystyle  \biggl(\frac{a}{n}\biggr)=-1, then the number a is a quadratic nonresidue modulo the odd integer n, i.e. the equation x^2 \equiv a \ (\text{mod} \ n) has no solutions. However, the value of \displaystyle  \biggl(\frac{a}{n}\biggr)=1 does not imply that a is a quadratic residue modulo n. For example, \displaystyle  \biggl(\frac{2}{15}\biggr)=1 but the equation x^2 \equiv 2 \ (\text{mod} \ 15) has no solutions. Note that both equations x^2 \equiv 2 \ (\text{mod} \ 3) and x^2 \equiv 2 \ (\text{mod} \ 5) have no solutions. This means that the value of \displaystyle  \biggl(\frac{2}{15}\biggr)=1 is the product of two Legendre symbols of -1.

Theorem 1
Let n be an odd positive integer. Let a be such that \text{GCD}(a,n)=1. Then If a is a quadratic residue modulo n, then \displaystyle  \biggl(\frac{a}{n}\biggr)=1. The converse does not hold if n is not a prime.

Proof
Suppose that a is a quadratic residue modulo n, i.e. the equation x^2 \equiv a \ (\text{mod} \ n) has a solution. Let n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t} be the prime factorization of n. Let m_i=p_i^{e_i} for each i. By the Chinese remainder theorem, the equation x^2 \equiv a \ (\text{mod} \ m_i) has a solution for each i=1,2,\cdots,t. it then follows that the equation x^2 \equiv a \ (\text{mod} \ p_i) has a solution too for each i=1,2,\cdots,t. Hence the Legendre symbol \displaystyle  \biggl(\frac{a}{p_i}\biggr)=1 for each i. It follows that the Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr)=1. \square

For the second question, the rules that are obeyed by the Legendre symbol are also obeyed by the Jacobi symbol. Some of the rules are easily seen to carry over to the Jacobi symbol. The fact that the law of quadratic reciprocity and the two supplements are obeyed by the Jacobi symbol is not entirely obvious from the definition. However the proof is not difficult. We give a complete proof here.

Lemma 2
Let a and b be odd positive integers. The following two conditions hold.

    \displaystyle \frac{a-1}{2} \times \frac{b-1}{2} \equiv \frac{ab-1}{2} \ (\text{mod} \ 2)

    \displaystyle \frac{a^2-1}{8} \times \frac{b^2-1}{8} \equiv \frac{(ab)^2-1}{8} \ (\text{mod} \ 2)

Proof
The lemma is established by the following derivation:

    \displaystyle \frac{ab-1}{2}-\biggl[\frac{a-1}{2}+\frac{b-1}{2} \biggr]=\frac{ab-a-b+1}{2}=\frac{(a-1)(b-1)}{2}

    \displaystyle \frac{(ab)^2-1}{8}-\biggl[\frac{a^2-1}{8}+\frac{b^2-1}{8} \biggr]=\frac{(ab)^2-a^2-b^2+1}{8}=\frac{(a^2-1)(b^2-1)}{8}

Because both a and b are odd integers, the right-hand-side of both equations are even integers and thus \equiv 0 \ (\text{mod} \ 2). \square

Theorem 3 (Properties of Jacobi Symbol)

  1. \displaystyle  \biggl(\frac{a}{n}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } \text{GCD}(a,n) >1 \\          \pm 1 &\ \text{if } \text{GCD}(a,n)=1 \end{array} \right.
  2. \text{ }

  3. If n is a prime, then the Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr) coincides with the Legendre symbol \displaystyle  \biggl(\frac{a}{n}\biggr).
  4. \text{ }

  5. If a \equiv b \ (\text{mod} \ n), then \displaystyle  \biggl(\frac{a}{n}\biggr)=\biggl(\frac{b}{n}\biggr).
  6. \text{ }

  7. The Jacobi symbol is multiplicative when the bottom argument is fixed, i.e. \displaystyle  \biggl(\frac{ab}{n}\biggr)=\biggl(\frac{a}{n}\biggr) \biggl(\frac{b}{n}\biggr).
  8. \text{ }

  9. The Jacobi symbol is multiplicative when the upper argument is fixed, i.e. \displaystyle  \biggl(\frac{a}{mn}\biggr)=\biggl(\frac{a}{m}\biggr) \biggl(\frac{a}{n}\biggr).
  10. \text{ }

  11. (The law of quadratic reciprocity)
    Let a and b be relatively prime odd positive integers. Then

      \displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)=(-1)^{(a-1)/2 \times (b-1)/2}

      Equivalently, \displaystyle  \biggl(\frac{a}{b}\biggr) = \left\{ \begin{array}{rl}           \displaystyle  \biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv 1 \ (\text{mod} \ 4) \text{ or }  b \equiv 1 \ (\text{mod} \ 4) \\         \displaystyle  -\biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv b \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

  12. (First supplement to the law of quadratic reciprocity)
    Let n be an odd positive integer. Then

      \displaystyle  \biggl(\frac{-1}{n}\biggr)=(-1)^{(n-1)/2}.

      Equivalently, \displaystyle  \biggl(\frac{-1}{n}\biggr) = \left\{ \begin{array}{rl}           1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 4) \\         -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

  13. (Second supplement to the law of quadratic reciprocity)
    Let n be an odd positive integer. Then

      \displaystyle  \biggl(\frac{2}{n}\biggr)=(-1)^{(n^2-1)/8}.

      Equivalently, \displaystyle  \biggl(\frac{2}{n}\biggr) = \left\{ \begin{array}{rl}           1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 8) \text{ or } n \equiv 7 \ (\text{mod} \ 8) \\         -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 8) \text{ or } n \equiv 5 \ (\text{mod} \ 8) \end{array} \right.

Proof
For the first bullet point, if the top argument and the bottom argument have a prime factor in common, then one of the Legendre symbols that make up the Jacobi symbol is zero. If the top argument and the bottom argument have no prime factor in common, then all the Legendre symbols that make up the Jacobi symbol is either 1 or -1.

The second point is clear. If the bottom argument is an odd prime, the definition of Jacobi symbol leads to the Legendre symbol.

For bullet points 3, 4 and 5, simply write out the Jacobi symbol and then use the corresponding properties of the Legendre symbol.

Now the proof of bullet point 6 (the law of quadratic reciprocity). Let a and b be relatively prime. Let a=p_1 \times p_2 \times \cdots \times p_w and b=q_1 \times q_2 \times \cdots \times q_t be their prime factorizations. Note that the primes p_i are not necessarily distinct and the primes q_i are not necessarily distinct. However, p_i \ne q_j since a and b are relatively prime. Consider the following derivation of the product \displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr).

    \displaystyle \begin{aligned}\biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)&=\prod \limits_{i=1}^t \biggl(\frac{a}{q_i}\biggr) \ \prod \limits_{j=1}^w \biggl(\frac{b}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{j=1}^w \prod \limits_{i=1}^t \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{i=1}^t \prod \limits_{j=1}^w \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w (-1)^{(p_j-1)/2 \times (q_i-1)/2} \\&=(-1)^E \end{aligned}

    where

    \displaystyle E=\sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]

The bullet point 6 is established after the quantity E is simplified as follows:

    \displaystyle \begin{aligned} \sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]&=\sum_j \biggl[\sum_i \frac{q_i-1}{2}\biggr] \frac{p_j-1}{2} \\&\equiv \sum_j \biggl[ \frac{b-1}{2}\biggr] \frac{p_j-1}{2} \ \ \ \text{ Use Lemma 2}\\&\equiv \frac{b-1}{2} \sum_j  \frac{p_j-1}{2} \\&\equiv \frac{b-1}{2} \frac{a-1}{2} \ (\text{mod} \ 2) \ \ \ \text{ Use Lemma 2}  \end{aligned}

Now consider the bullet point #7 (the first supplement to the law of quadratic reciprocity). The proof is an induction proof on the number of prime factors of n. If n is a prime, then it is done. So we assume n=p_1 \times p_2 (not necessarily distinct). Consider the following derivation:

    \displaystyle \begin{aligned} \biggl(\frac{-1}{n}\biggr)&=\biggl(\frac{-1}{p_1}\biggr) \biggl(\frac{-1}{p_2}\biggr) \\&=(-1)^{(p_1-1)/2} \ (-1)^{(p_2-1)/2} \\&=(-1)^{(p_1-1)/2+(p_2-1)/2} \\&\equiv (-1)^{(p_1 \times p_2 -1)/2} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n -1)/2} \ (\text{mod} \ 2) \end{aligned}

It is a straightforward argument that whenever the property is true for n being a product of k primes, the property is true for n being a product of k+1 primes. Thus bullet 7 is established.

The proof of bullet point 8 (the second supplement to the law of quadratic reciprocity) is also an induction proof on the number of prime factors of n. The most important case is the of two prime factors.

    \displaystyle \begin{aligned} \biggl(\frac{2}{n}\biggr)&=\biggl(\frac{2}{p_1}\biggr) \biggl(\frac{2}{p_2}\biggr) \\&=(-1)^{(p_1^2-1)/8} \ (-1)^{(p_2^2-1)/8} \\&=(-1)^{(p_1^2-1)/8+(p_2^2-1)/8} \\&\equiv (-1)^{((p_1 \times p_2)^2 -1)/8} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n^2 -1)/8} \ (\text{mod} \ 2) \end{aligned}

With the 2-case established, it is straightforward to carry out the remainder of the induction proof of bullet 8. \square

____________________________________________________________________________

Examples

Example 1
Evaluate \displaystyle  \biggl(\frac{1783}{7523}\biggr), an example where both the upper and lower arguments are primes. In the previous post, the example is calculated using only Legendre symbol. Here we work it in Jacobi symbol. As much as possible, we flip the symbol without factoring.

    \displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \ \ *\\&=\biggl(\frac{1783}{391}\biggr) \\&=\biggl(\frac{219}{391}\biggr) \ \ *\\&=-\biggl(\frac{391}{219}\biggr) \\&=-\biggl(\frac{172}{219}\biggr) \\&=-\biggl(\frac{2}{219}\biggr)^2 \biggl(\frac{43}{219}\biggr) \\&=-\biggl(-1\biggr)^2 (-1) \biggl(\frac{219}{43}\biggr) \\&=\biggl(\frac{4}{43}\biggr) \\&=1 \end{aligned}

One advantage of using Jacobi symbol is that when the upper argument is an odd integer that is not prime, we can still flip it (the steps with *). Then reduce and then flip again until we reach a point with small numbers. Thinking in Legendre symbol only, the steps with * cannot be flipped. As Jacobi symbols, they can be flipped freely as long as the arguments are odd integers. The advantage may not be apparent in this example. When the composite integers are large to the point that their factorizations are in effect not obtainable, this advantage is huge. \square

Example 2
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 1298351, an odd prime and a= 756479. This is Example 2 in this previous post. The number a is not a prime. Here we use Jacobi symbol to demonstrate that factoring is not needed. We can start by flipping. We have the following derivation.

    \displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=-\biggl(\frac{1298351}{756479}\biggr) \\&=-\biggl(\frac{541872}{756479}\biggr) \\&=-\biggl(\frac{2}{756479}\biggr)^4 \times \biggl(\frac{33867}{756479}\biggr) \\&=-\biggl(1\biggr)^4 \times (-1) \biggl(\frac{756479}{33867}\biggr)  \\&=\biggl(\frac{11405}{33867}\biggr) \\&=\biggl(\frac{33867}{11405}\biggr) \\&=\biggl(\frac{11057}{11405}\biggr) \\&=\biggl(\frac{11405}{11057}\biggr) \\&=\biggl(\frac{348}{11057}\biggr) \\&=\biggl(\frac{2}{11057}\biggr)^2 \biggl(\frac{87}{11057} \biggr) \\&=\biggl(1\biggr)^2  \biggl(\frac{11057}{87} \biggr) \\&=\biggl(\frac{8}{87}\biggr) \\&=\biggl(\frac{2}{87} \biggr)^3 \\&=1 \end{aligned}

Note that the original symbol to evaluate is a Legendre symbol. The interim steps are done with Jacobi symbol as much as possible. With the Jacobi way, the symbol is flipped, reduced and flipped again multiple times. The derivation seems long. However, the flip-reduce-flip is much faster than factoring when the numbers involved are large. \square

Example 3
Evaluate \displaystyle  \biggl(\frac{a}{n}\biggr) where n= 12408107 and a= 4852777. Both numbers are not prime. The symbol has to be evaluated as a Jacobi symbol.

    \displaystyle \begin{aligned} \biggl(\frac{4852777}{12408107}\biggr)&=\biggl(\frac{12408107}{4852777}\biggr)  \\&= \biggl(\frac{2702553}{4852777}\biggr) \\&= \biggl(\frac{4852777}{2702553}\biggr) \\&= \biggl(\frac{2150224}{2702553}\biggr) \\&= \biggl(\frac{2}{2702553}\biggr)^4 \biggl(\frac{134389}{2702553}\biggr) \\&= \biggl(1\biggr)^4 \biggl(\frac{2702553}{134389}\biggr) \\&= \biggl(\frac{14773}{134389}\biggr) \\&= \biggl(\frac{134389}{14773}\biggr) \\&= \biggl(\frac{1432}{14773}\biggr) \\&= \biggl(\frac{2}{14773}\biggr)^3 \biggl(\frac{179}{14773}\biggr) \\&= \biggl(-1\biggr)^3 \biggl(\frac{14773}{179}\biggr) \\&= - \biggl(\frac{95}{179}\biggr) \\&= - (-1) \biggl(\frac{179}{95}\biggr) \\&=\biggl(\frac{84}{95}\biggr) \\&=\biggl(\frac{2}{95}\biggr)^2 \biggl(\frac{21}{95}\biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{95}{21}\biggr) \\&=\biggl(\frac{11}{21}\biggr) \\&=\biggl(\frac{21}{11}\biggr) \\&=\biggl(\frac{10}{11}\biggr) \\&=\biggl(\frac{2}{11}\biggr) \biggl(\frac{5}{11}\biggr) \\&=\biggl(-1\biggr) \biggl(\frac{11}{5}\biggr) \\&=-\biggl(\frac{6}{5}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \biggl(\frac{3}{5}\biggr) \\&=-\biggl(-1\biggr) \biggl(\frac{5}{3}\biggr) \\&=\biggl(\frac{2}{3}\biggr) \\&=-1 \end{aligned}

The above derivation seems long in that there are quite a few steps. But many of the steps are flip-reduce-flip-reduce that are easy to do. The steps are all done without factoring, except when the top argument is an even number. The Jacobi symbol \displaystyle  \biggl(\frac{a}{n}\biggr) is -1. In this case, it gives definite information about the status of quadratic nonresidues. We know for sure that a is a quadratic nonresidue modulo the odd integer n, i.e. the equation x^2 \equiv a \ (\text{mod} \ n) has no solutions. \square

Example 4
Evaluate \displaystyle  \biggl(\frac{a}{n}\biggr) where n= 48746413 and a= 17327467. Both numbers are not prime. As in Example 3, the symbol is evaluated using Jacobi symbol.

    \displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{48746413}{17327467}\biggr)  \\&=\biggl(\frac{14091479}{17327467}\biggr) \\&=-\biggl(\frac{17327467}{14091479}\biggr) \\&=-\biggl(\frac{3236168}{14091479}\biggr) \\&=-\biggl(\frac{2}{14091479}\biggr)^3 \biggl(\frac{404521}{14091479}\biggr) \\&=-\biggl(1\biggr)^3 \biggl(\frac{14091479}{404521}\biggr) \\&=- \biggl(\frac{337765}{404521}\biggr) \\&=- \biggl(\frac{404521}{337765}\biggr) \\&=- \biggl(\frac{66756}{337765}\biggr) \\&=- \biggl(\frac{2}{337765}\biggr)^2 \biggl(\frac{16689}{337765}\biggr) \\&=- \biggl(-1\biggr)^2 \biggl(\frac{337765}{16689}\biggr) \\&=-\biggl(\frac{3985}{16689}\biggr) \\&=-\biggl(\frac{16689}{3985}\biggr) \\&=-\biggl(\frac{749}{3985}\biggr) \\&=-\biggl(\frac{3985}{749}\biggr) \\&=-\biggl(\frac{240}{749}\biggr) \\&=-\biggl(\frac{2}{749}\biggr)^4 \biggl(\frac{15}{749}\biggr) \\&=-\biggl(-1\biggr)^4 \biggl(\frac{749}{15}\biggr) \\&=-\biggl(\frac{14}{15}\biggr) \\&=-\biggl(\frac{-1}{15}\biggr)\\&=-(-1)\\&=1 \end{aligned}

The result of \displaystyle  \biggl(\frac{a}{n}\biggr)=1 gives ambiguous information about the status of a= 17327467 being a quadratic residue or nonresidue modulo n= 48746413. In this case, the Jacobi symbol cannot tell us whether the equation x^2 \equiv a \ (\text{mod} \ n) has a solution. In such a case, the only way to know the status of quadratic residue is to know some additional information, namely the factoring of the numbers. This example is small enough that a= 3049 x 5683 and n= 7109 x 6857. With this information, the Jacobi symbol can be set up as follows:

    \displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{17327467}{7109}\biggr) \biggl(\frac{17327467}{6857}\biggr)=(-1) (-1)=1   \end{aligned}

By knowing the factoring of n, the original Jacobi symbol is a product of two Legendre symbols. It can be shown that both of these Legendre symbols are -1. These two Legendre symbols corresponds to these two equations: x^2 \equiv a \ (\text{mod} \ 7109) and x^2 \equiv a \ (\text{mod} \ 6857). The Legendre values of -1 indicate that these two equations have no solutions. By the Chinese remainder theorem, the equation x^2 \equiv a \ (\text{mod} \ 7109 \times 6857) has no solutions. Hence a= 17327467 is a quadratic nonresidue modulo n= 48746413=7109 x 6857. \square

____________________________________________________________________________

Comments

One versatile feature of the Jacobi symbol is that it can be used in evaluating the Legendre symbol, as shown in Example 1 and Example 2. The original Legendre symbol in Example 1 have arguments that are both odd prime and thus can be flipped right away. However, there are numbers in the interim steps that are odd and not prime. With the use of the Jacobi symbol, these interim numbers do have to be factored. The original Legendre symbol in Example 2 has a top argument that is odd and not prime. Treating it as a Jacobi symbol, it can be flipped right away. When numbers involved in Legendre symbol evaluation are large such that the factoring is not obtainable, the Jacobi symbol can be flipped and reduced and flipped again to obtain the answer of the Legendre symbol. The Jacobi symbol plays an outsize role in the evaluation of the Legendre symbol and thus is a pivotal tool in determining whether a number is a quadratic residue modulo an odd prime p or the solvability of the equation x^2 \equiv a \ (\text{mod} \ p).

Example 3 shows that when the Jacobi symbol produces the value of -1, the top argument a is a quadratic nonresidue modulo the lower argument n. Example 4 shows that when the Jacobi symbol produces the value of 1, the picture is murky. In such a case, settling the question of whether the top argument a is a quadratic nonresidue modulo the lower argument n requires additional information. Example 4 shows that if we can factor the lower argument n, then evaluating the individual Legendre symbols (based on the prime factors) will help answer the original question. This points to the possibility that solving the equation x^2 \equiv a \ (\text{mod} \ n) is not feasible when the factorization of a large composite modulus n is not obtainable.

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

The Legendre symbol

The law of quadratic reciprocity is a beautiful result. It is also an excellent tool to answer the question: given an odd prime p, and given that a is an integer such that a and p are relatively prime, is a is a quadratic residue modulo p, in other words, is the equation x^2 \equiv a \ (\text{mod} \ p) solvable? Using the law of quadratic reciprocity requires the evaluation of the Legendre symbol. The focus of this post is on the Legendre symbol as well as related concepts of quadratic residues and the law of quadratic residues. The versatility of the law of quadratic reciprocity is demonstrated with examples.

____________________________________________________________________________

Quadratic Residues

The setting is that the modulus in question is an odd prime p. Consider an integer a such that a and p are relatively prime, i.e. having no common prime factor. The number a is said to be a quadratic residue modulo p if the equation x^2 \equiv a \ (\text{mod} \ p) has an integer solution in x. Another way to say this is that a is a quadratic residue modulo p if there exists a square root of a modulo p (a square root would be a solution to the equation). If the integer a is not a quadratic residue modulo p, we say that a is a quadratic nonresidue modulo p. If the context is clear, the word quadratic can be omitted. We can then say a is a residue modulo p or a is a nonresidue modulo p.

Since every integer is congruent modulo p to one of the numbers in the set \mathbb{Z}_p=\left\{0,1,2,\cdots,p-1 \right\}, the integers a can be considered from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} (the non-zero elements of \mathbb{Z}_p).

Let’s look at a quick example. Let p=11. Squaring each number in \mathbb{Z}_{11} produces the set \left\{0^2,1^2,2^2,\cdots,10^2 \right\}. Reducing modulo 11 produces the set \left\{0,1,4,9,5,3 \right\}. Thus the integers 1, 3, 4, 5 and 9 are quadratic residues modulo 11. The square roots of each residue are the solutions to the equation x^2 \equiv a \ (\text{mod} \ 11). For a=3, the solutions are x = 5 and 6. There are two square roots of 3 modulo 11, namely 5 and 6.

When the modulus is small, it is easy to find all quadratic residues simply by squaring all the numbers in \mathbb{Z}_p^*. The focus in this post is on how to use the law of quadratic reciprocity to determine whether a given a is a quadratic residue modulo a large odd prime p.

To check whether the integer a is a quadratic residue modulo an odd prime p, the most important idea, before considering the law of reciprocity, is to check the modular exponentiation a^{(p-1)/2} \ (\text{mod} \ p). If the result is congruent to 1 modulo p, then a is a quadratic residue modulo p. If the result is congruent to -1 modulo p, then a is a quadratic nonresidue modulo p. This is called Euler’s Criterion (proved here). For clarity, it is stated below.

Theorem 1 (Euler’s Criterion)
Let p be an odd prime. Let a be an integer that is relatively prime to p. Then the integer a is a quadratic residue modulo p if and only if \displaystyle a^{(p-1)/2} \equiv 1 \ (\text{mod} \ p). On the other hand, the integer a is a quadratic nonresidue modulo p if and only if \displaystyle a^{(p-1)/2} \equiv -1 \ (\text{mod} \ p).

According to Euler’s Criterion, the task of checking for the status of quadratic residue is a matter of performing a modular exponentiation. This can be done using software or a calculator for modular arithmetic. If so desired, the exponentiation can also be programmed using the fast powering algorithm.

Though Euler’s Criterion (with a calculator for modular arithmetic) is a sure fire way for checking the status of quadratic residues, the law of quadratic reciprocity can simplify the task even further. As the examples below will show, checking the status of quadratic residues using the law of reciprocity may require no modular exponentiation at all and if exponentiation is required, it is of a much smaller size.

Euler’s Criterion also gives us several basic facts about quadratic residues.

Theorem 2
Let p be an odd prime. The following properties are true:

  • If a and b are both residues modulo p, then the product a \times b is a residue modulo p.
  • If If a and b are both nonresidues modulo p, then the product a \times b is a residue modulo p.
  • If a and b are such that one of them is a residue modulo p and the other is a nonresidue modulo p, then the product a \times b is a nonresidue modulo p.

Theorem 2 says that the product of two integers of the same types (both residues or both nonresidues) is always a residue modulo the odd prime p. The product of two integers of different types is always a nonresidue modulo the odd prime p. The theorem follows from Euler’s criterion and from the fact that (ab)^{(p-1)/2}=a^{(p-1)/2} \times b^{(p-1)/2}.

In arithmetic modulo a prime p, there exists a primitive root modulo p and that any primitive root generates by powering all the integers that are relatively prime to the modulus p. Let g be a primitive root modulo an odd prime p. It then follows that the quadratic residues modulo p are the even powers of g and the nonresidues are the odd powers of g. A related fact is that when p is an odd prime and when a and p are relatively prime, the equation x^2 \equiv a \ (\text{mod} \ p) either has two solutions or has no solutions.

Theorem 3
Let g be a primitive root modulo an odd prime p. For any a that is relatively prime to p, the following is true:

  • a is a quadratic residue modulo p if and only if a is of the form a \equiv g^{2k} \ (\text{mod} \ p) for some positive integer k,
  • a is a quadratic nonresidue modulo p if and only if a is of the form a \equiv g^{2k+1} \ (\text{mod} \ p) for some positive integer k.
  • (proved here)

Theorem 4
Let p be an odd prime. For any a that is relatively prime to p, the equation x^2 \equiv a \ (\text{mod} \ p) either has two solutions or has no solutions (proved here).

____________________________________________________________________________

Legendre Symbol

The law of quadratic reciprocity is stated using the Legendre symbol. For an odd prime p and for an integer a that is relatively prime to p, the symbol \displaystyle \biggl(\frac{a}{p}\biggr) is defined as follows:

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}                      1 &\ \text{if }  a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if }  a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

One obvious and important observation is that Euler’s Criterion can be restated as follows:

Theorem 1a (Euler’s Criterion)
Let p be an odd prime. Let a be an integer that is relatively prime to p. Then \displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p).

In the above definition, the lower argument of the Legendre symbol is always an odd prime and the upper argument is an integer that is relatively prime to the lower argument. To smooth out some statements involving the Legendre symbol and to make it easier to define the Jacobi symbol in the next post, we relax the Legendre symbol by making \displaystyle \biggl(\frac{a}{p}\biggr)=0 whenever a and p are not relatively prime, i.e. a \equiv 0 \ (\text{mod} \ p). The Legendre symbol can be broaden slightly by the following:

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\           1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

Here’s some useful basic facts about the Legendre symbol.

Theorem 5
Let p be an odd prime. The following properties hold:

  • The Legendre symbol is periodic with respect to the top argument, i.e. if a \equiv b \ (\text{mod} \ p), then \displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr).
  • The Legendre symbol is multiplicative with respect to the top argument, i.e. \displaystyle \biggl(\frac{ab}{p}\biggr)=\biggl(\frac{a}{p}\biggr) \times \biggl(\frac{b}{p}\biggr).
  • If a \equiv 0 \ (\text{mod} \ p), then \displaystyle  \biggl(\frac{a^2}{p}\biggr)=0. If a \not \equiv 0 \ (\text{mod} \ p), then \displaystyle  \biggl(\frac{a^2}{p}\biggr)=1.

The first bullet point in Theorem 5 is easily verified based on the definition of the Legendre symbol. For the case a \equiv 0 \ (\text{mod} \ p), the other facts in Theorem 5 are easily verified. For the case a \not \equiv 0 \ (\text{mod} \ p), the second bullet point follows from Theorem 2, i.e. the fact that the product of two residues and the product of two nonresidues are both residues modulo an odd prime and that the product of a residue and a nonresidue is a nonresidue modulo an odd prime. The second part of the third bullet point is true since any integer that is a square is a quadratic residue.

____________________________________________________________________________

Law of Quadratic Reciprocity

The law of reciprocity can ease the calculation of the Legendre symbol when both the upper and lower arguments are distinct odd primes. Theorem 6 is the law of reciprocity and Theorem 7 and Theorem 8 are two supplements to the law that can round out the calculation. After stating the theorems, we demonstrate with some examples.

Theorem 6 (the law of quadratic reciprocity)

    Let p and q be two distinct odd prime numbers. Both of the following statements hold.

      \displaystyle  \biggl(\frac{q}{p}\biggr) \displaystyle \biggl(\frac{p}{q}\biggr)=(-1)^{(p-1)/2 \times (q-1)/2}

      Equivalently and more explicitly,

      \displaystyle  \biggl(\frac{q}{p}\biggr) = \left\{ \begin{array}{rl}                      \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \text{ or } q \equiv 1 \ (\text{mod} \ 4)\\          \displaystyle  -\biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv q \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

Theorem 7 (first supplement to the law of quadratic reciprocity)

    Let p be an odd prime number. The following statement holds.

      \displaystyle  \biggl(\frac{-1}{p}\biggr) = (-1)^{(p-1)/2} = \left\{ \begin{array}{rl}                      1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4)\\          -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

Theorem 8 (second supplement to the law of quadratic reciprocity)

    Let p be an odd prime number. The following statement holds.

      \displaystyle  \biggl(\frac{2}{p}\biggr) =(-1)^{(p^2-1)/8}= \left\{ \begin{array}{rl}                      1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 8) \text{ or } p \equiv 7 \ (\text{mod} \ 8)\\          -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 8) \text{ or } p \equiv 5 \ (\text{mod} \ 8) \end{array} \right.

Theorem 6 shows how to flip the Legendre symbol if both the upper and lower arguments are distinct odd primes. As long as one of the primes is congruent to 1 modulo 4, we can safely flip the symbol. If both primes are not congruent to 1 modulo 4, we can still flip the symbol except that we have to attach a minus sign. Theorem 7 (the first supplement) indicates when -1 (or p-1) is a quadratic residue an odd prime p. In words, -1 is a residue modulo p if dividing p by 4 gives the remainder of 1. Otherwise -1 is a nonresidue modulo p. Theorem 8 (the second supplement) indicates when 2 is a residue modulo an odd prime p. In words, 2 is a residue modulo p if dividing p by 8 leaves a remainder of 1 or 7. Otherwise 2 is a nonresidue modulo p.

____________________________________________________________________________

Examples

Example 1
Evaluate \displaystyle  \biggl(\frac{1783}{7523}\biggr), an example where both the upper and lower arguments in the Legendre symbol are primes.

    \displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \\&=-\biggl(\frac{17}{1783}\biggr) \times \biggl(\frac{23}{1783}\biggr) \\&=-\biggl(\frac{1783}{17}\biggr) \times (-1) \biggl(\frac{1783}{23}\biggr) \\&=\biggl(\frac{15}{17}\biggr) \times \biggl(\frac{12}{23}\biggr) \\&=\biggl(\frac{3}{17}\biggr) \times \biggl(\frac{5}{17}\biggr) \times \biggl(\frac{2}{23}\biggr)^2 \times \biggl(\frac{3}{23}\biggr) \\&=\biggl(\frac{17}{3}\biggr) \times \biggl(\frac{17}{5}\biggr) \times \biggl(1\biggr)^2 \times (-1)\biggl(\frac{23}{3}\biggr) \\&=-\biggl(\frac{2}{3}\biggr) \times \biggl(\frac{2}{5}\biggr) \times  \biggl(\frac{2}{3}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \\&=-(-1) \\&=1 \end{aligned}

The above derivation is a repeated use of Theorems 5, 6 and 8. The idea is to flip the Legendre symbols to make the lower arguments smaller. Then reduce the upper arguments and then factor the upper arguments. Then flip again until reaching a Legendre symbol of \displaystyle \biggl(\frac{2}{5}\biggr), which is easy to solve.

It then follows that 1783 is a quadratic residue modulo the odd prime 7523. The answer can be confirmed by using Euler’s Criterion. Note that 1783^{3761} \equiv 1 \ (\text{mod} \ 7523). \square

Example 2
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 1298351, an odd prime and a= 756479.

The number a is not a prime and is factored as a=353 \times 2143. We have the following derivation.

    \displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=\biggl(\frac{353}{1298351}\biggr) \times \biggl(\frac{2143}{1298351}\biggr) \\&=\biggl(\frac{1298351}{353}\biggr) \times (-1)\biggl(\frac{1298351}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{1836}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{2}{2143}\biggr)^2 \times \biggl(\frac{3}{2143}\biggr)^3 \times \biggl(\frac{17}{2143}\biggr)  \\&=-\biggl(\frac{353}{17}\biggr) \times \biggl(1\biggr)^2 \times (-1) \biggl(\frac{2143}{3}\biggr)^3 \times \biggl(\frac{2143}{17}\biggr) \\&=\biggl(\frac{13}{17}\biggr) \times  \biggl(\frac{1}{3}\biggr)^3 \times \biggl(\frac{1}{17}\biggr) \\&=\biggl(\frac{17}{13}\biggr) \times  \biggl(1\biggr)^3 \times \biggl(1\biggr) \\&=\biggl(\frac{4}{13}\biggr) \\&=1 \end{aligned}

The evaluation of the Legendre symbols in this example does not start with a flipping since the upper argument 756479 is not a prime. Instead, we start with factoring the upper argument into prime factors and then proceed with a series of flipping, reducing and factoring. \square

Example 3
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 569, an odd prime and a= 1610280.

    \displaystyle \begin{aligned} \biggl(\frac{1610280}{569}\biggr)&=\biggl(\frac{3}{569}\biggr)^4 \times \biggl(\frac{5}{569}\biggr) \times \biggl(\frac{7}{569}\biggr) \times \biggl(\frac{568}{569}\biggr) \\&= \biggl(\frac{569}{3}\biggr)^4 \times \biggl(\frac{569}{5}\biggr) \times \biggl(\frac{569}{7}\biggr) \times \biggl(\frac{-1}{569}\biggr) \\&= \biggl(\frac{2}{3}\biggr)^4 \times \biggl(\frac{4}{5}\biggr) \times \biggl(\frac{2}{7}\biggr) \times \biggl(1\biggr) \\&= \biggl(-1\biggr)^4 \times \biggl(1\biggr) \times \biggl(1\biggr) \\&=1 \end{aligned}

This example can also be evaluated by first reducing 1610280 modulo 569. \square

____________________________________________________________________________

Comment

The law of quadratic reciprocity is a deep and powerful result. It guides the evaluation of Legendre symbols in an attempt to answer whether a number is a quadratic residue modulo an odd prime. The law of reciprocity as represented above requires that the lower argument in the Legendre symbol is an odd prime. When the upper argument is an odd number that is not a prime, there is no way to flip it (based on the law of reciprocity using the Legendre symbol). In Example 2, the evaluation of the Legendre symbol cannot begin until the top argument is factored. The factoring in Example 2 is possible since the number is small. When the number is large, factoring may not always be feasible. It turns out that the Legendre symbol has a generalization, called the Jacobi symbol, that is even more versatile and is defined in the next post.

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Speeding up modular exponentiation using CRT

This is the fifth post in a series of posts on the Chinese remainder theorem (CRT). When solving a congruence equation with a composite modulus, it is often easier to convert the problem to one of solving several congruence equations with smaller moduli that are primes or powers of primes. Then combine the individual solutions using the Chinese remainder theorem. In this post, we demonstrate this process for modular exponentiation x \equiv c^d \ (\text{mod} \ m) where the exponent d and the modulus m are large. Given x \equiv c^d \ (\text{mod} \ m), the algorithm discussed here is to produce a system of equations with smaller moduli and exponents that give the same answer as for the original problem.

The previous posts in the series on CRT: first post; second post; third post; fourth post

____________________________________________________________________________

Preliminary discussion

The exponentiation c^d is usually programmed using the fast powering algorithm. The CRT method will convert the exponentiation c^d to several exponentiations that involve much smaller exponents and moduli, thus greatly reducing the calculation time, in particular speeding up the fast powering algorithm. One application of the CRT method is to improve the run time of the decryption process in the RSA algorithm (up to four times faster).

As already mentioned, the goal of the algorithm discussed here is to produce an equivalent system of linear congruence equations. Once this system is produced, the Chinese remainder theorem only guarantees a solution and does not actually produce a solution. So we need to know how to Chinese remainder, i.e. using an algorithm for solving a simultaneous linear congruences. We can use the one discussed here (the first method) or here (the second method). The following examples are worked using the second method.

The CRT algorithm discussed here makes use of Euler’s theorem, which states that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) whenever a and the modulus m are relatively prime where \phi(m) is the phi function evaluated at m. For this reason, the algorithm requires the evaluation of the phi function.

When calculating c^d \ (\text{mod} \ m), the use of the phi function \phi(m) is to reduce the exponent d by the largest multiple of \phi(m). For example, since \phi(17)=16 and 2^{16} \equiv 1 \ (\text{mod} \ 17), the problem of 2^{250} \ (\text{mod} \ 17) is converted to finding 2^{10} \ (\text{mod} \ 17). Here, the original exponent of 250 is reduced to 10 after taking out the largest multiple of 16. Note that 10 \equiv 250 \ (\text{mod} \ \phi(17)=16). In general, we want to replace the original exponent d by a smaller exponent d_1 where d_1 \equiv d \ (\text{mod} \ \phi(m)).

____________________________________________________________________________

Examples

In the following three examples, we use the algorithm discussed here to solve systems of linear congruence equations (this is the iterative approach). These examples are by no means realistic since the numbers used are small. So they are for demonstration of how CRT works.

Example 1
Calculate x \equiv 2^{3163} \ (\text{mod} \ 3969).

First, factor the modulus 3969=3^4 \times 7^2=81 \times 49. Now the problem is converted to solving the following system of two equations:

    x \equiv 2^{3163} \ (\text{mod} \ 81)

    x \equiv 2^{3163} \ (\text{mod} \ 49)

By CRT, any solution to the two equations is also a solution to the original equation. However, the exponent of 3163 should first be reduced. To this end, calculate the phi function, where \phi(3^4)=3^2 \cdot (3-1)=54 and \phi(7^2)=7 \cdot (7-1)=42. We should reduce from 3163 the largest multiple of 54 in the first equation and reduce the largest multiple of 42 in the second equation. In other words, reduce the exponent 3163 modulo the two phi function values:

    3163 \equiv 31 \ (\text{mod} \ 54)

    3163 \equiv 13 \ (\text{mod} \ 42)

As a result, we solve the following two equations:

    x \equiv 2^{3163} \equiv 2^{31} \equiv 65 \ (\text{mod} \ 81)

    x \equiv 2^{3163} \equiv 2^{13} \equiv 9 \ (\text{mod} \ 49)

Note that the original exponentiation 2^{3163} is turned into the easier ones of 2^{31} and 2^{13}. The following gives the solution to the above two equations.

    \displaystyle \begin{aligned} x_0&=65+81 \cdot 23 \cdot (9-65) \ (\text{mod} \ 3969)  \\&\equiv -104263 \ (\text{mod} \ 3969) \\&\equiv 2900 \ (\text{mod} \ 3969) \end{aligned}

    where 23 is obtained by solving for y in 81y \equiv 1 \ (\text{mod} \ 49)

By CRT, the answer to the original problem is 2^{3163} \equiv 2900 \ (\text{mod} \ 3969). \square

Example 2
Calculate x \equiv 3^{3163} \ (\text{mod} \ 3969).

In this example, the number 3 and the modulus 3969 are not relatively prime. The CRT method still applies. As in Example 1, the problem can be reduced in the following way:

    x \equiv 3^{3163} \equiv 3^{31} \equiv 0 \ (\text{mod} \ 81)

    x \equiv 2^{3163} \equiv 3^{13} \equiv 10 \ (\text{mod} \ 49)

The first equation is congruent to 0 since 3^{31} contains 81 as a factor. The following gives the solution to the above two equations:

    \displaystyle \begin{aligned} x_0&=0+81 \cdot 23 \cdot (10-0) \ (\text{mod} \ 3969)  \\&\equiv 18630 \ (\text{mod} \ 3969) \\&\equiv 2754 \ (\text{mod} \ 3969) \end{aligned}

By CRT, the answer to the original problem is 3^{3163} \equiv 2754 \ (\text{mod} \ 3969). \square

Example 3
The above 2 examples use small numbers to illustrate the CRT technique. In this example, we use slightly larger numbers. Calculate x \equiv 355^{d} \ (\text{mod} \ m) where d=\text{1,759,695,794} and m=\text{3,055,933,789}=1277 \cdot 1439 \cdot 1663.

As in the other examples, we break up the problem in three congruences. The three factors of the modulus are prime numbers. Thus we reduce the exponent d by multiples of a prime factor less one.

    \text{1,759,695,794} \equiv 1198 \ (\text{mod} \ 1276)

    \text{1,759,695,794} \equiv 814 \ (\text{mod} \ 1438)

    \text{1,759,695,794} \equiv 110 \ (\text{mod} \ 1662)

Then the original problem is transformed to solving the following three equations.

    x \equiv 355^{d} \equiv 355^{1198} \equiv 189 \ (\text{mod} \ 1277)

    x \equiv 355^{d} \equiv 355^{814} \equiv 1010 \ (\text{mod} \ 1439)

    x \equiv 355^{d} \equiv 355^{110} \equiv 315 \ (\text{mod} \ 1663)

Notice that the original exponentiation is transformed to the smaller ones of 355^{1198}, 355^{814} and 355^{315}. The remaining task is to solve the system of three equations. One way to find to solution to the above three equations is to use the iterative approach, starting with the solution x_1=189 to the first equation. Then find the solution x_2 to the first two equations and then the solution x_3 to all three equations.

    \displaystyle \begin{aligned} x_2&=189+1277 \cdot 151 \cdot (1010-189) \ (\text{mod} \ 1277 \cdot 1439)  \\&\equiv 158311156 \ (\text{mod} \ 1837603) \\&\equiv 277298 \ (\text{mod} \ 1837603) \end{aligned}

    where 151 is obtained by solving for y in 1277y \equiv 1 \ (\text{mod} \ 1439)

    \displaystyle \begin{aligned} x_3&=277298+(1277 \cdot 1439) \cdot 970 \cdot (315-277298) \ (\text{mod} \ 1277 \cdot 1439 \cdot 1663)  \\&\equiv 277298+1782474910 \cdot (-276983) \ (\text{mod} \ m) \\&\equiv 277298+1414954310 \ (\text{mod} \ m) \\&\equiv 1415231608 \ (\text{mod} \ m) \end{aligned}

    where 970 is obtained by solving for y in (1277 \cdot 1439) y \equiv 1 \ (\text{mod} \ 1663)

By CRT, the answer to the original problem is 355^{d} \equiv 1415231608 \ (\text{mod} \ m). \square

____________________________________________________________________________

The CRT algorithm to speed exponentiation

Suppose we wish to evaluate x \equiv c^{d} \ (\text{mod} \ m) where the prime factorization of m is m=p_1^{n_1} \cdot p_2^{n_2} \cdots p_t^{n_t}. The numbers p_i are distinct prime numbers and each exponent n_i \ge 1. To prepare for the calculation, do the following:

    Let m_i=p_i^{n_i} for each i.

    Calculate \phi(m_i) for each i.

Case 1. The base c and the modulus m are relatively prime.
Then the answer to the original exponentiation problem is identical to the solution to the following system of t congruence equations:

    x \equiv c^{d_1} \ (\text{mod} \ m_1)

    x \equiv c^{d_2} \ (\text{mod} \ m_2)

    \cdots

    x \equiv c^{d_t} \ (\text{mod} \ m_t)

where d_i \equiv d \ (\text{mod} \ \phi(m_i)) for each i. If possible, each c^{d_i} should be reduced modulo m_i.

Case 2. The base c and the modulus m are not relatively prime.
In this case, c and m have prime factors in common (at least one p_i). The idea here is that for any p_i that is a prime factor of c, the equation x \equiv c^{d_i} \ (\text{mod} \ m_i) in Case 1 is replaced by x \equiv 0 \ (\text{mod} \ m_i). Then solve the resulting system of equations (see Example 2). Essentially, Case 2 can fall under Case 1 with c^{d_i} being congruent to zero. We call out Case 2 for the sake of clarity.

The original exponentiation c^d boils down to solving an appropriate system of CRT congruences as described above. Once the equivalent system of congruences is set up, use the algorithm discussed here or here to do Chinese remaindering.

Comment
Both Case 1 and Case 2 produce a system of linear congruence equations that have identical solution to the original equation. This is a result of using CRT (see Theorem D and Theorem G here). The savings in the calculation come in the form of the smaller exponentiations in the resulting congruence equations.

In Case 2, some of the congruence equations are x \equiv 0. This is because the base c and some moduli m_i are not relatively prime. For these moduli, c^{d_i} would contain p_i^{n_i} as a factor (assuming that d_i \ge n_i). Hence, x \equiv c^{d_i} \equiv 0 \ (\text{mod} \ m_i).

The two-equation case
When the modulus is the product of two factors that are relatively prime, the CRT algorithm involves only two equations. We write out the solution explicitly for this case. To evaluate x \equiv c^{d} \ (\text{mod} \ m) where m=m_1 \cdot m_2 and m_1 and m_2 are relatively prime, solve the following system of two equations,

    x \equiv c^{d_1} \ (\text{mod} \ m_1)

    x \equiv c^{d_2} \ (\text{mod} \ m_2)

The solution is x \equiv  c^{d_1}+m_1 \cdot v_1 \cdot (c^{d_2}-c^{d_1}) \ (\text{mod} \ m) where v_1 is the multiplicative inverse of m_1 modulo m_2. If possible, each c^{d_i} should be reduced modulo m_i.

____________________________________________________________________________

RSA application

The algorithm to speed the exponentiation is possible because the factorization of the modulus m is known (as a result, the values of \phi(m_i) are known). Knowing the values of \phi(m_i) makes it possible to reduce the large exponent d. For this reason, the decryption process in the RSA algorithm is a perfect place to apply the CRT technique described here.

With the RSA cryptosystem, a public key consists of N and e, where N is a large modulus that is a product of two large primes p and q (the two primes are not published) and e is the encryption exponent. Say Bob is the originator of the RSA public key. Bob also generates a private key, which is a number d that is used for decrypting any messages that he receives. The number d must be kept private. The prime factors p and q must also be kept secret since knowing p and q can derive d.

Suppose that Alice has a message to send to Bob. She can do so using the published key of N and e through the exponentiation c \equiv m^e \ (\text{mod} \ N). Here, m is the plaintext (the message to be sent) and c is the ciphertext (the encrypted message). Upon receiving the ciphertext c, Bob can then decrypt through the exponentiation m \equiv c^d \ (\text{mod} \ N) where d is the decryption exponent. In realistic RSA calculation, the public modulus N and the private decryption exponent d are large integers (N is at minimum a 2048-bit number). With CRT, the decryption can be reduced to two much smaller exponentiations. The effect can be at least four times faster.

We illustrate this with an example. This is a toy example since the numbers used are small. It is only intended as an illustration.

Example 4
Suppose the public key consists of N=\text{17,086,049} and e=65537. Bob has the additional information of N=p \cdot q where p=3863 and q=4423, which are kept secret. Knowing p and q allows Bob to compute d=\text{5,731,241}. Suppose that Bob receives a message c= 4831984 from Alice. Use the CRT approach to find the plaintext m.

The exponentiation is m \equiv 4831984^{5731241} \ (\text{mod} \ N), which is equivalent to the following two equations by CRT:

    m \equiv 4831984^{5731241} \ (\text{mod} \ 3863)

    m \equiv 4831984^{5731241} \ (\text{mod} \ 4423)

which is further simplified to:

    m \equiv 4831984^{5731241} \equiv 4831984^{33} \equiv 3084 \ (\text{mod} \ 3863)

    m \equiv 4831984^{5731241} \equiv 4831984^{329} \equiv 1436 \ (\text{mod} \ 4423)

where 33 \equiv 5731241 \ (\text{mod} \ 3862) and 329 \equiv 5731241 \ (\text{mod} \ 4422). Then the following is the plaintext (the original message).

    \displaystyle \begin{aligned} m&=3084+3863 \cdot 1319 \cdot (1436-3084) \ (\text{mod} \ 3863 \cdot 4423)  \\&\equiv 3084+5095297 \cdot (-1648) \ (\text{mod} \ N) \\&\equiv 9289736 \ (\text{mod} \ N) \end{aligned}

    where 1319 is obtained by solving for y in 3683y \equiv 1 \ (\text{mod} \ 4423)

The answer is 4831984^{5731241} \equiv 9289736 \ (\text{mod} \ N). \square

____________________________________________________________________________

Closing comment

In conclusion, we state the explcit formula for providing the CRT answer to the RSA decryption.

    m \equiv  c^{d_p}+p \cdot p_{inv} \cdot (c^{d_q}-c^{d_p}) \ (\text{mod} \ p \cdot q) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where d_p \equiv d \ (\text{mod} \ p-1), d_q \equiv d \ (\text{mod} \ q-1) and p_{inv} is the multiplicative inverse of p modulo q.

The decryption formula of (1) represends tremendous saving in calculation (up to four times faster). It is possible only for the holder of the RSA private key. It requires knowledge of the decryption exponent d, which is calculated from the factors p and q of the modulus N.
____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

The primitive root theorem revisited

The primitive root theorem lists out all possible values of m for which primitive roots exist in the modulo m arithmetic. The theorem is proved in this previous post and several blog posts leading to it. In this post, we reorganize the proof and add some additional information. The proof of the primitive root theorem detailed below shows that the list of values of the moduli m is very restrictive and, in addition, that such moduli m are such that there are no extra square root beside 1 and -1. The crux of the argument is a lemma that indicates that most moduli have a third square root of 1 in addition to 1 and -1. The proof is also an opportunity for applying the Chinese remainder theorem (usually abbreviated CRT).

____________________________________________________________________________

The primitive root theorem

In this post, m is a positive integer that serves as the modulus. Given m, it is of interest to know all the integers a where 1 \le a <m and that a and the modulus m are relatively prime. The number of such values of a is denoted by \phi(m) (this is called the phi function). For example, for m=11, \phi(11)=10. For m=10, \phi(10)=4 since there are only 4 numbers that are relatively prime to 10, namely 1, 3, 7, and 9.

A positive integer g is said to be a primitive root modulo m if \phi(m) is the least positive integer x such that g^x \equiv 1 \ (\text{mod} \ m). If g is said to be a primitive root modulo m, it is necessary that g and the modulus m are relatively prime. This is because of this basic fact: a and the modulus m are relatively prime if and only a \cdot b \equiv 1 \ (\text{mod} \ m) if and only of a^t \equiv 1 \ (\text{mod} \ m) for some integer t. The middle condition is saying that a has a multiplicative modulo m.

The following lemma is alluded to at the beginning. The idea will used through the proof of the primitive root theorem. So it is extracted as a lemma to make the argument easier to follow.

Lemma 1
Let c and d be integers such that c>2 and d>2 and such that c and d are relatively prime. Let m=c \cdot d. Then there exist x_0 such that x_0 \not \equiv \pm 1 \ (\text{mod} \ m) and such that x_0^2 \equiv 1 \ (\text{mod} \ m), i.e. x_0 is a third square root of 1 modulo m that is neither 1 nor -1.

Proof
Consider the two equations x \equiv 1 \ (\text{mod} \ c) and x \equiv -1 \ (\text{mod} \ d). By the Chinese remainder theorem, there is a solution x_0 to this system of equations. We have x_0^2 \equiv 1 \ (\text{mod} \ c) and x_0^2 \equiv 1 \ (\text{mod} \ d). By the Chinese remainder theorem again, x_0^2 \equiv 1 \ (\text{mod} \ m). There are three possibilities for x_0, 1, -1 or another value. If x_0 \equiv 1 \ (\text{mod} \ m), then 1 \equiv -1 \ (\text{mod} \ d), which means d \lvert 2, contradicting that d>2. Similarly, x_0 \equiv -1 \ (\text{mod} \ m) would lead to c \lvert 2, which contradicts c>2. The only possibility is that x_0 \not \equiv \pm 1 \ (\text{mod} \ m). \square

The proof of Lemma 1 makes use of CRT twice. Lemma 1 will be used several times in the proof of 2 \longrightarrow 3 in the primitive root theorem.

The Primitive Root Theorem
Let m be a positive integer. Then the following conditions are equivalent:

  1. There exists a primitive root modulo m.
  2. The equation x^2 \equiv 1 \ (\text{mod} \ m) has no solution outside of \pm 1 modulo m. In other words, the only square roots of 1 modulo m are \pm 1.
  3. The only possibilities for m are:
    • m=2,
    • m=4,
    • m is the power of an odd prime,
    • m is twice the power of an odd prime.

Proof
1 \longrightarrow 2
Suppose that g is a primitive root modulo m. Suppose that condition 2 does not hold. As a result, there exists some positive integer a \not \equiv \pm 1 \ (\text{mod} \ m) such that a^2 \equiv 1 \ (\text{mod} \ m). Since g is a primitive root modulo m, a \equiv g^h \ (\text{mod} \ m) for some integer integer h with 1 \le h < \phi(m) (see Theorem 5 here). If h = \phi(m), then a \equiv 1 \ (\text{mod} \ m). Thus 1 \le h < \phi(m).

Furthermore, a^2 \equiv g^{2h} \equiv 1 \ (\text{mod} \ m). We have \phi(m) \le 2h, since \phi(m) is the least power x such that g^x is congruent to 1 modulo m. Since g^{2h}=g^{\phi(m)} g^{2h-\phi(m)}, g^{2h} \equiv g^{2h-\phi(m)} \equiv 1 \ (\text{mod} \ m). We have \phi(m) \le 2h-\phi(m) since \phi(m) is the least power x such that g^x is congruent to 1 modulo m. The last inequality leads to \phi(m) \le h, contradicting the earlier observation of h < \phi(m). Thus condition 2 must holds if condition 1 is true.

2 \longrightarrow 3
We show that for any m outside of the four possibilities listed in condition 3, condition 2 does not hold. This means that if condition 2 holds for m, m must be one of the four possibilities. We consider the cases of m even and m odd separately.

Case 1. The modulus m is odd. Since m is not the power of one single odd prime, it must be the product of two or more powers of odd primes. Let m=c \cdot d where c a power of an odd prime and d is the product of one ore more powers of odd primes. It is clear that c and d are relatively prime. It is also the case that c>2 and d>2 since each of them has at least one odd prime factor. By Lemma 1, there exists a square root x_0 of 1 such that x_0 \not \equiv \pm 1 \ (\text{mod} \ m).

For the second case, m is even. We break this up into two cases. One is that m is a power of 2. The other is that m is not a power of 2. In these two cases, the goal is still to show that if m is outside of the four possibilities in condition 3, then condition 2 does not hold.

Case 2a. The modulus m is a power of 2.
Then m=2^h where h \ge 3. In this case, we can actually exhibit a square root that is neither 1 nor -1. Define x_0=2^{h-1}-1. Since h \ge 3, x_0>1. Consider the following derivation:

    \displaystyle x_0^2=(2^{h-1}-1)^2=2^{2(h-1)}-2^h+1=2^h (2^{h-2}-1)+1

The above derivation shows that x_0^2 \equiv 1 \ (\text{mod} \ m=2^h). It is clear that x_0 \not \equiv \pm 1 \ (\text{mod} \ 2^h).

Case 2b. The modulus m is not a power of 2.
Since m is even and m is not a power of 2, it must be that m=2^k \times q where q is odd. Either q is the power of an odd prime or it is not. If q is the power of an odd prime, then k \ge 2. If q is not the power of an odd prime (i.e. q is of case 1 above), then k \ge 1. To make the argument clear, we consider the two sub cases separately.

Case 2b-1. The modulus m=2^k \times p^j where k \ge 2, j \ge 1 and p is an odd prime.
Let c=2^k and d=p^j. Note that m=c \cdot d. By Lemma 1, there exists a square root x_0 of 1 modulo m such that x_0 \not \equiv \pm 1 \ (\text{mod} \ m).

Case 2b-2. The modulus m=2^k \times b where k \ge 1 and b is an odd integer that is not the power of an odd prime.
Consider the prime factorization of b, say b=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t} where t \ge 2. Let c=2^k \cdot p_1^{e_1} and d=p_2^{e_2} \cdots p_t^{e_t}. We can also apply Lemma 1 to obtain a square root of 1 modulo m=c \cdot d that is neither 1 nor -1.

3 \longrightarrow 1
It is clear that there are primitive roots modulo both m=2 and m=4. For the case of power of an odd prime, see this previous post. For the case of twice the power of an odd prime, see this previous post. \square

____________________________________________________________________________

Comments

Lemma 1 plays a prominent role in the proof of the direction 2 \longrightarrow 3. Lemma 1 shows that it is easy to find moduli that have a third square root of 1 (other than 1 and -1). As the primitive root theorem shows, having a third square root of 1 is the condition that kills the possibility of having a primitive root. Lemma 1 and the primitive root theorem speak to different sides of the same coin. One tells us that moduli with no primitive roots are easy to find. The other says that only in rare cases do you find moduli that admit primitive roots, namely the moduli that are not product of two factors, each of which is greater than 2, that are relatively prime. The proof of 2 \longrightarrow 3 may seem tedious (by listing out all cases that satisfy Lemma 1). The key to understanding the proof is through Lemma 1.

____________________________________________________________________________

\copyright \ 2015 \text{ by Dan Ma}

Counting Fermat witnesses

For the Fermat primality test, looking for a Fermat witness is the name of the game. Given an integer n for which the “prime or composite” status is not known, if you can find a Fermat witness for n, you can conclude decisively that n is not a prime number. If n is a composite number in reality (but the status is not known to you), how likely is it to find a Fermat witness? In other words, when you use the Fermat primality test on a composite integer, what is the probability of the test giving the correct answer? Or what is the probability of making a mistake? In this post we answer these questions by having a detailed look at Fermat witnesses. This is done through a theorem (see Theorem 1 below) and by counting the numbers of Fermat witnesses of a series of composite integers.

____________________________________________________________________________

Fermat witness

What is a Fermat witness? A Fermat witness is a number that violates the conclusion of Fermat’s little theorem. Here’s the theorem:

    Fermat’s little theorem
    If n is a prime number and if a is an integer that is relatively prime to n, then a^{n-1} \equiv 1 \ (\text{mod} \ n).

If we can find a number a that is relatively prime to n such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we know for sure that n is composite. Such a number a is said to be a Fermat witness for the compositeness of n. For convenience, we say that a potential Fermat witness for the compositeness of n is any integer a in the interval 1<a<n that is relatively prime to n.

To use the Fermat primality test on the integer n, we examine a random sample of potential Fermat witnesses for n. If one of the potential Fermat witnesses in the sample turns out to be a Fermat witness for n, we know with certainty that n is composite. If none of the potential Fermat witnesses in the random sample is a Fermat witness, then n is a likely a prime number.

As with most diagnostic tests, a test can make two types of mistakes – false positives or false negatives. For primality testing, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number. For the Fermat test, there is no false negative (see Case 1 in the next section). If the Fermat test gives a negative result, it would be a true negative.

On the other hand, the Fermat test can give a false positive. There are two cases for false positives. In one case (Case 2a), the probability of a false positive can be made as low as possible. For the other case (Case 2b), the probability of a false positive is virtually 100%.

____________________________________________________________________________

Looking at different cases

If n is a prime number in reality (but the status is not known before the testing), the Fermat test will always give the correct result. The Fermat test will never make the mistake of declaring a prime number as composite. What if is n is a composite number in reality? How would the test behave? It turns out that if n is a composite number that has a Fermat witness, the test is an effective probabilistic primality test. On the other hand, if n is a composite number that has no Fermat witness, the test will identify n as a prime number (so the test fails completely). Here’s the cases we just describe:

  • Case 1. n is a prime number.
  • Case 2. n is a composite number.
    • Case 2a. n is a composite number that has a Fermat witness.
    • Case 2b. n is a composite number that has no Fermat witness.

Let’s look at the cases in more details. If n is a prime number in reality, then it satisfies Fermat’s little theorem. The congruence a^{n-1} \equiv 1 \ (\text{mod} \ n) is always true. So the Fermat test will always give the correct result when the number being tested is a prime number in reality. In Case 1, it will never identify a prime number as a composite number. As mentioned above, the probability of a false negative is zero.

If n is a composite number that has at least one Fermat witness, there is a chance that the Fermat test can identify n as a prime (i.e. a false positive). However, the probability of making a mistake can be reducdd by increasing the number of potential witnesses to be calculated. Indeed, if we sample k potential witnesses, there is at most a 2^{-k} chance of getting a wrong result. In Case 2a, the probability of error can be made so small that it is practically zero for all practical purposes. In this case, the Fermat test can work truly as a probabilistic primality test. In this case, the probability of a false positive can be made as small as possible.

The last case (Case 2b) is the weakest link in the Fermat test. Any composite number n such that a^{n-1} \equiv 1 \ (\text{mod} \ n) for all a relatively prime to n is said to be a Carmichael number. When the Fermat test is applied on such a number, it will never give the correct conclusion (i.e. it will always give a false positive). It does not matter how many potential Fermat witnesses that are calculated. In fact, calculating a^{n-1} \ (\text{mod} \ n) for a large number of values of a can lead one to believe that this number n is a prime number. In this case, the probability of a false positive is virtually 100%. So the case of Carmichael numbers cannot be totally ignored. There are infinitely many Carmichael numbers (proved in 1994). Fortunately, it is harder and harder to find Carmichael numbers as you move up in the number line. For an illustration that Carmichael numbers are rare, see a discussion in this previous post.

We will see below that for the composite numbers in Case 2a, the Fermat test has a very small probability of a false positive (identifying a composite number as a prime number). On the other hand, for the composite numbers in Case 2b, the Fermat test has a 100% probability of a false positive. Of course, when you test a number for primality, you do not know in advance what case it is. Thus the presence of Carmichael numbers is a concern.

____________________________________________________________________________

A floor for the count of Fermat witnesses

Theorem 1 below sets a floor for Fermat witnesses. Once again, in this theorem we only care about the composite numbers that have at least one Fermat witness. Recall that a potential Fermat witness for the compositeness of n is an integer a in the interval 1<a<n such that a and n are relatively prime, i.e., \text{GCD}(a,n) = 1.

Theorem 1
Let n be a composite integer that has at least one Fermat witness. Then at least half of the potential witnesses for the compositeness of n are Fermat witnesses.

Proof of Theorem 1
Let a be a Fermat witness for n. We claim that if b is a potential Fermat witness that is not a Fermat witness, then a \cdot b is a Fermat witness for n. First of all, a \cdot b is relatively prime to n. Note that the product if two numbers, each of which is relatively prime to n, is once again a number that is relatively prime to n (see Lemma 4 in this previous post). Thus a \cdot b is a potential Fermat witness for n. The following shows that a \cdot b is a Fermat witness for n.

    (a \cdot b)^{n-1}=a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)

In the above derivation, we use the fact that a is a Fermat witness for n and that b is not a Fermat witness for n, which means that b^{n-1} \equiv 1 \ (\text{mod} \ n).

If all the potential Fermat witnesses are Fermat witnesses, then we are done since the conclusion of the theorem is true. Assume that at least one potential Fermat witness is not a Fermat witness. In fact, the following enumerates all potential Fermat witnesses that are not Fermat witnesses:

    b_1,\ b_2,\ \cdots, \ b_k

where k \ge 1 and b_i \not \equiv b_j \ (\text{mod} \ n) for all i \ne j. By the claim established earlier, the following numbers are all Fermat witnesses for n.

    a \cdot b_1, \ a \cdot b_2, \ \cdots, \ a \cdot b_k

The above Fermat witnesses are all distinct. If ab_i \equiv ab_j \ (\text{mod} \ n) where i \ne j, then we can multiply both sides by a^{-1} and obtain b_i \equiv b_j \ (\text{mod} \ n), which is not possible. What we have proved is that if there exists one Fermat witness for n and if there are k many distinct potential Fermat witnesses that are not Fermat witnesses, then there are at least k many Fermat witnesses for n. This means that at most half of the potential witnesses are non-Fermat witnesses (if there are more than half, we get a contradiction). Thus at least half of the potential Fermat witnesses are Fermat witnesses. \blacksquare

There is another way to state Theorem 1. Recall that Euler’s phi function \phi(n) is defined to be the number of integers a in the interval 1<a<n that are relatively prime to n. In other words, \phi(n) is the count of the potential Fermat witnesses for n. With this in mind, Theorem 1 can be restated as the following:

Corollary 2
Let n be a composite integer that has at least one Fermat witness. Then the number of Fermat witnesses for the compositeness of n is at least \displaystyle \frac{\phi(n)}{2}.

____________________________________________________________________________

The significance of Theorem 1

Theorem 1 gives a floor on Fermat witnesses for one type of composite numbers, namely the composite numbers that have at least one Fermat witness (put another way, the composite numbers that are not Carmichael numbers). More importantly, Theorem 1 allows us to estimate the probability of error when using the Fermat test on such composite numbers.

When applying the Fermat test on a composite integer n that has at least one Fermat witness, the only scenario in which the Fermat test can make an error (aside from calculation errors of course) is that all the random selections of a are not Fermat witnesses. So you are so unlucky that you happen to pick all values of a that are not Fermat witnesses. What is the probability of that?

Randomly select a potential Fermat witness for n, there is at least 50% chance that it is a Fermat witness and at most 50% chance that it is not a Fermat witness. We have the following statement:

    If n is a composite number that has at least one Fermat witness, and if you sample one potential Fermat witness for n, there is at most a 50% chance that it is not a Fermat witness.

If you pick two values of a at random, there is at most 0.5^2=0.25=25 \% chance that both are not Fermat witnesses. If you pick three values of a at random, there is at most 0.5^3=0.125=12.5 \% chance that you pick non-Fermat witnesses three times in a row. If you pick 10 potential witnesses at random, there is at most

    0.5^{10}=0.000977=0.0977 \%

chance that all ten values of a are not Fermat witnesses. In general, we can make the following statement:

    If n is a composite number that has at least one Fermat witness, then when sampling k many potential Fermat witnesses for n, the probability that none of the k potential witnesses is Fermat witness is 0.5^k.

Recall that the only scenario in which the Fermat test can make a mistake when testing a composite number belonging to Case 2a is that the random sample of values of a contains only non-Fermat witnesses. Thus when the sample size is large, the probability of error can be made very small.

The bottom line is that the more potential witnesses you sample, the less likely that you won’t pick a Fermat witness (i.e., it is more likely that you will pick one). Picking a Fermat witness is essentially a coin toss. If you toss a fair coin many times, it is not likely to get all tails (it is likely to get at least one head).

The calculation for each potential witness a is a^{n-1} \ (\text{mod} \ n). Exponentiation in modular arithmetic can be done using the fast powering algorithm, which is an efficient algorithm that involves repeated squarings and multiplications. Thus if the composite number n happens to be a composite number with a Fermat witness, the Fermat test is very efficient (when used with the fast powering algorithm) and accurate.

Of course, when you test the primality of a number, you do not know which case it belongs to. If you want to avoid the case of Carmichael numbers entirely, you might want to try a primality test that can detect Carmichael numbers (e.g. the Miller-Rabin test).

____________________________________________________________________________

Counting examples

To reinforce the discussion in the previous sections, we count the Fermat witnesses for 10 integers. They are all small numbers (the largest one is a little over 200,000). These integers are composite integers that are not Carmichael numbers. So each has at least one Fermat witness. To count the witnesses, we create a computer program to determine the witness status for all a in 1<a<n that are relatively prime to n. The counts are shown in the following matrix.

    Composite integers that are not Carmichael numbers

    \left[\begin{array}{rrrrrrrrr}      \text{ } & \text{ } & \text{ } & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} \\      n & \text{ } & \phi(n) & \text{ } & \text{Yes} & \text{ } & \text{No} & \text{ } & \text{Yes} \ \% \\      \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }  \\      91 & \text{ } & 72 & \text{ } & 36 & \text{ } & 36  & \text{ } & 50 \% \\      221 & \text{ } & 192 & \text{ } & 176 & \text{ } & 16 & \text{ } & 91.67 \% \\      341 & \text{ } & 300 & \text{ } & 200 & \text{ } & 100 & \text{ } & 66.67 \% \\      5,777 & \text{ } & 5,616 & \text{ } & 5,600 & \text{ } & 16 & \text{ } & 99.72 \% \\      10,873 & \text{ } & 10,660 & \text{ } & 10,656 & \text{ } & 4 & \text{ } & 99.96 \% \\      21,809 & \text{ } & 21,504 & \text{ } & 21,248 & \text{ } & 256 & \text{ } & 98.81 \% \\      50,113 & \text{ } & 42,948 & \text{ } & 42,912 & \text{ } & 36& \text{ } & 99.92 \%  \\      73,861 & \text{ } & 73,312 & \text{ } & 73,296 & \text{ } & 16 & \text{ } & 99.98 \% \\       100,097 & \text{ } & 99,396 & \text{ } & 99,392 & \text{ } & 4 & \text{ } & 100 \% \\      201,217 & \text{ } & 200,260 & \text{ } & 200,256 & \text{ } & 4 & \text{ } & 100 \%    \end{array}\right]

The first column is the 10 integers from 91 to 201,217. The second column is Euler’s phi function, which is the count of all integers a that are relatively prime to n, which is the count of the potential Fermat witnesses for n. For n=91, there are 72 potential Fermat witnesses where exactly half are Fermat witnesses. For the other numbers on the list, the percentages of Fermat witnesses are a lot more than 50%. In fact, for most of them, the Fermat witness percentages are over 99%. For the last two numbers on the list the percentage is virtually 100%.

Consider 201,217, the last number on the list. Applying the Fermat test on the number, it will be hard not to pick up a Fermat witness. With only 4 potential witnesses that are not Fermat witness, it is certain to find one Fermat witness when more than 4 numbers are sampled. In fact, even if just 4 numbers are sampled, there is a virtually 100% chance that a Fermat witness will be found.

Take the number in the above table that has the largest number of non-Fermat witnesses (n=21,809), which has 256 non-Fermat witnesses. It has 21,504 potential witnesses. Out of a random sample of 20 such potential Fermat witnesses, the probability that none of them is a Fermat witness is 3.24 \cdot 10^{-39}, which is practically zero.

The above calculations show that for composite numbers that have at least one Fermat witness, the Fermat test is very accurate with a very high probability. The key is to sample a large enough number of potential witnesses. However for Carmichael numbers, it is totally different story.

As discussed earlier, a Carmichael number is a composite number n that has no Fermat witnesses. Specifically a composite number n is a Carmichael number if a^{n-1} \equiv 1 \ (\text{mod} \ n) for all integers a such that 1<a<n and a and n are relatively prime. The following table is a demonstration of this property.

    The first ten Carmichael numbers

    \left[\begin{array}{rrrrrrrrr}      \text{ } & \text{ } & \text{ } & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} \\      n & \text{ } & \phi(n) & \text{ } & \text{Yes} & \text{ } & \text{No} & \text{ } & \text{Yes} \ \% \\      \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }  \\      561 & \text{ } & 320 & \text{ } & 0 & \text{ } & 320  & \text{ } & 0 \% \\      1,105 & \text{ } & 768 & \text{ } & 0 & \text{ } & 768 & \text{ } & 0 \% \\      1,729 & \text{ } & 1,296 & \text{ } & 0 & \text{ } & 1,296 & \text{ } & 0 \% \\      2,465 & \text{ } & 1,792 & \text{ } & 0 & \text{ } & 1,792 & \text{ } & 0 \% \\      2,821 & \text{ } & 2,160 & \text{ } & 0 & \text{ } & 2,160 & \text{ } & 0 \% \\      6,601 & \text{ } & 5,280 & \text{ } & 0 & \text{ } & 5,280 & \text{ } & 0 \% \\      8,911 & \text{ } & 7,128 & \text{ } & 0 & \text{ } & 7,128& \text{ } & 0 \%  \\      10,585 & \text{ } & 8,064 & \text{ } & 0 & \text{ } & 8,064 & \text{ } & 0 \% \\       15,841 & \text{ } & 12,960 & \text{ } & 0 & \text{ } & 12,960 & \text{ } & 0 \% \\      29,341 & \text{ } & 25,920 & \text{ } & 0 & \text{ } & 25,920 & \text{ } & 0 \%    \end{array}\right]

The above table lists out the first ten Carmichael numbers. Though we can show that each one of them is a Carmichael number by using the Korselt’s Criterion (see here but you have to first factor the numbers). We calculate the Fermat witness status for each potential witness for each n in the table. The above table is a visual demonstration of the fact that the column for the Fermat witnesses is entirely zero! So if you happen to test the primality on such numbers using the Fermat test, you will conclude that they are prime numbers unless you happen to sample a value of a whose GCD with n is greater than one (i.e., the only way you can determine the compositeness of a Carmichael number is to stumble into a GCD witness).

Fermat test does what it does well with the exception of Carmichael numbers. As mentioned earlier, if you want to avoid the trap of working with Carmichael numbers (as rare as they are), you can always switch to a test that will always detect Carmichael numbers (e.g. Miller-Rabin test).

____________________________________________________________________________

\copyright \ 2014 \text{ by Dan Ma}