Notes on Primality Testing And Public Key Cryptography Part 1: Randomized Algorithms Miller–Rabin and Solovay–Strassen Tests Jean Gallier and Jocelyn Quaintance Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104, USA e-mail: [email protected] (cid:13)c Jean Gallier September 8, 2017 Contents Contents 2 1 Introduction 5 1.1 Prime Numbers and Composite Numbers . . . . . . . . . . . . . . . . . . . . 5 1.2 Methods for Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Some Tests for Compositeness . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Public Key Cryptography 13 2.1 Public Key Cryptography; The RSA System . . . . . . . . . . . . . . . . . . 13 2.2 Correctness of The RSA System . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Algorithms for Computing Powers and Inverses Modulo m . . . . . . . . . . 22 2.4 Finding Large Primes; Signatures; Safety of RSA . . . . . . . . . . . . . . . 26 3 Primality Testing Using Randomized Algorithms 33 4 Basic Facts About Groups, and Number Theory 37 4.1 Groups, Subgroups, Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.4 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.5 Which Groups (Z/nZ)∗ Have Primitive Roots . . . . . . . . . . . . . . . . . 73 4.6 The Structure of Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 The Miller–Rabin Test 81 5.1 Square Roots of Unity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.2 The Fermat Test; F-Witnesses and F-Liars . . . . . . . . . . . . . . . . . . . 84 5.3 Carmichael Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.4 The Miller–Rabin Test; MR-Witnesses and MR-Liars . . . . . . . . . . . . . 91 5.5 The Monier–Rabin Bound on the Size of the Set of MR-Liars . . . . . . . . . 104 5.6 The Least MR-Witness for n . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6 The Solovay–Strassen Test 113 6.1 Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.2 The Legendre Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 2 CONTENTS 3 6.3 The Jacobi Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.4 The Solovay–Strassen Test; E-Witnesses and E-Liars . . . . . . . . . . . . . 125 6.5 The Quadratic Reciprocity Law . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.6 A Randomized Algorithm to Find a Square Root mod p . . . . . . . . . . . 132 6.7 Proof of the Quadratic Reciprocity Law . . . . . . . . . . . . . . . . . . . . . 138 6.8 Eisenstein’s Proof of the Quadratic Reciprocity Law . . . . . . . . . . . . . . 143 6.9 Strong Pseudoprimes are Euler Pseudoprimes . . . . . . . . . . . . . . . . . 146 Bibliography 151 4 CONTENTS Chapter 1 Introduction 1.1 Prime Numbers and Composite Numbers Prime numbers have fascinated mathematicians and more generally curious minds for thou- sands of years. What is a prime number? Well, 2,3,5,7,11,13,...,9973 are prime numbers. The defining property of a prime number p is that it is a positive integer p ≥ 2 that is only divisible by 1 and p. Equivalently, p is prime if and only if p is a positive integer p ≥ 2 that is not divisible by any integer m such that 2 ≤ m < p. A positive integer n ≥ 2 which is not prime is called composite. Observe that the number 1 is considered neither a prime nor a composite. For example, 6 = 2·3 is composite. Is 3215031751 composite? Yes, because 3215031751 = 151·751·28351. The above number has the remarkable property of being the only composite integer less than 25·109 which a strong pseudoprime simultaneously to the bases 2,3,5,7; see Definition 5.5, and Ribenboim [17] (Chapter 2, Section XI). Even though the definition of primality is very simple, the structure of the set of prime numbers is highly nontrivial. The prime numbers are the basic building blocks of the natu- ral numbers because of the following theorem bearing the impressive name of fundamental theorem of arithmetic. Theorem 1.1. Every natural number n ≥ 2 has a unique factorization n = pi1pi2···pik, 1 2 k where the exponents i ,...,i are positive integers and p < p < ··· < p are primes. 1 k 1 2 k Every book on number theory has a proof of Theorem 1.1. The proof is not difficult and uses induction. It has two parts. The first part shows the existence of a factorization. The second part shows its uniqueness. For example, see Apostol [1] (Chapter 1, Theorem 1.10). How many prime numbers are there? Many! In fact, infinitely many. 5 6 CHAPTER 1. INTRODUCTION Theorem 1.2. The set of prime numbers is infinite. Proof. We give three proofs. These proofs only use the fact that every integer greater than 1 has some prime divisor. (1) (Euclid) Suppose that p = 2 < p = 3 < ··· < p are all the primes. Consider 1 2 m N = p p ···p + 1. The number N must be divisible by some prime p (p = N 1 2 m is possible). Then p must be one of the p , so p = p divides N − p p ···p = 1, i i 1 2 m contradicting the fact that p ≥ 2. i (2) (Kummer) Suppose that p = 2 < p = 3 < ··· < p are all the primes, as in (1), 1 2 m but this time let N = p p ···p . Observe that N > 2. The number N −1 must be 1 2 m divisible by one of the primes p (p = N −1 is possible). But if p divides N −1, then i i i p divides N −(N −1) = 1, a contradiction. i (3) (Hermite) We prove that for every natural number n ≥ 2, there is some prime p > n. Consider N = n! + 1. The number N must be divisible by some prime p (p = N is possible). Any prime p dividing N is distinct from 2,3,...,n, since otherwise p would divide N −n! = 1, a contradiction. There are many more proofs; see Ribenboim [17]. The problem of determining whether a given integer is prime is one of the better known and most easily understood problems of pure mathematics. This problem has caught the interest of mathematicians again and again for centuries. However, it was not until the 20th century that questions about primality testing and factoring were recognized as problems of practical importance, and a central part of applied mathematics. The advent of cryp- tographic systems that use large primes, such as RSA, was the main driving force for the development of fast and reliable methods for primality testing. Indeed, as we see in Chapter 2, in order to create RSA keys, one needs to produce large prime numbers. How do we do that? 1.2 Methods for Primality Testing The general strategy to test whether an integer n > 2 is prime or composite is to choose some property, say A, implied by primality, and to search for a counterexample a to this property for the number n, namely some a for which property A fails. We look for properties for which checking that a candidate a is indeed a countexample can be done quickly. Typically, together with the number n being tested for primality, some candidate coun- terexample a is supplied to an algorithm which runs a test to determine whether a is really a counterexample to property A for n. If the test says that a is a counterexample, also called a witness, then we know for sure that n is composite. If the algorithm reports that a is not a witness to the fact that n is composite, does this imply that n is prime? Unfortunately, no. 1.2. METHODS FOR PRIMALITY TESTING 7 This is because, there may be some composite number n and some candidate counterexample a for which the test says that a is not a countexample. Such a number a is called a liar. The other reason is that we haven’t tested all the candidate counterexamples a for n. The remedy is to make sure that we pick a property A such that if n is composite, then at least some candidate a is not a liar, and to test all potential countexamples a. The difficulty is that trying all candidate countexamples can be too expansive to be practical. The following analogy may be helpful to understand the nature of such a method. Sup- pose we have a population and we are interested in determining whether some individual is rich or not (we will say that someone who is not rich is poor). Every individual n has several bank accounts a, and there is a test to check whether a bank account a has a negative balance. The test has the property that if it is applied to an individual n and to one of its bank accounts a, and if it is positive (it says that account a has a negative balance), then the individual n is definitely poor. Note that we are assuming that a rich person is honest, namely that all bank accounts of a rich person have a nonnegative balance. This may be an unrealistic assumption. But if the test is negative (which means that account a has a nonnegative balance), this does not imply that n is rich. The problem is that the test may not be 100% reliable. It is possible that an individual n is poor, yet the test is negative for account a (account a has a nonnegative balance). We may also not have tested all the accounts of n. One way to deal with this problem is to use probabilities. If we know that the conditional probability that the test is positive for some account a given that n is poor is greater than p ≥ 1/2, then we can apply the test to (cid:96) accounts chosen independently at random. It is easy to show that the conditional probability that the test is negative (cid:96) times given that an individual n is poor is less than (1−p)(cid:96). For p close to 1 and (cid:96) large enough, this probability is very small. Thus, if we have high confidence in the test (p is close to 1) and if an individual n is poor, it is very unlikely that the test will be negative (cid:96) times. Actually, what we would really like to know is the conditional probability that the indi- vidual n is rich given that the test is negative (cid:96) times. If the probability that an individual n is rich is known, then the above conditional probability can be computed using Bayes’s rule. We will show how to do this later. A Monte Carlo algorithm does not give a definite answer. However, if (cid:96) is large enough (say (cid:96) = 100), then the conditional probability that the property of interest holds (here, n is rich), given that the test is negative (cid:96) times, is very close to 1. In other words, if (cid:96) is large enough and if the test is negative (cid:96) times, then we have high confidence that n is rich. There are two classes of primality testing algorithms: (1) Algorithms that try all possible countexamples, and for which the test does not lie. These algorithms give a definite answer: n is prime or n is composite. Until 2002, no algorithms running in polynomial time, were known. The situation changed in 2002 when a paper with the title “PRIMES is in P,” by Agrawal, Kayal and Saxena, 8 CHAPTER 1. INTRODUCTION appeared on the website of the Indian Institute of Technology at Kanpur, India. In this paper, it was shown that testing for primality has a deterministic (nonrandomized) algorithm that runs in polynomial time. Wewillnotdiscussalgorithmsofthistypehere,andinsteadreferthereadertoCrandall and Pomerance [3] and Ribenboim [17]. (2) Randomized algorithms. To avoid having problems with infinite events, we assume that we are testing numbers in some large finite interval I. Given any positive integer m ∈ I, some candidate witness a is chosen at random. We have a test which, given m and a potential witness a, determines whether or not a is indeed a witness to the fact that m is composite. Such an algorithm is a Monte Carlo algorithm, which means the following: (1) If the test is positive, then m ∈ I is composite. In terms of probabilities, this is expressed by saying that the conditional probability that m ∈ I is composite given that the test is positive is equal to 1. If we denote the event that some positive integer m ∈ I is composite by C, then we can express the above as Pr(C | test is positive) = 1. (2) If m ∈ I is composite, then the test is positive for at least 50% of the choices for a. We can express the above as 1 Pr(test is positive | C) ≥ . 2 This gives us a degree of confidence in the test. The contrapositive of (1) says that if m ∈ I is prime, then the test is negative. If we denote by P the event that some positive integer m ∈ I is prime, then this is expressed as Pr(test is negative | P) = 1. If we repeat the test (cid:96) times by picking independent potential witnesses, then the con- ditional probability that the test is negative (cid:96) times given that n is composite, written Pr(test is negative (cid:96) times | C), is given by Pr(test is negative (cid:96) times | C) = Pr(test is negative | C)(cid:96) = (1−Pr(test is positive | C))(cid:96) (cid:18) 1(cid:19)(cid:96) ≤ 1− 2 (cid:18)1(cid:19)(cid:96) = , 2 1.3. SOME TESTS FOR COMPOSITENESS 9 where we used Property (2) of a Monte Carlo algorithm that 1 Pr(test is positive | C) ≥ 2 and the independence of the trials. This confirms that if we run the algorithm (cid:96) times, then Pr(test is negative (cid:96) times | C) is very small. In other words, it is very unlikely that the test will lie (cid:96) times (is negative) given that the number m ∈ I is composite. If the probabilty Pr(P) of the event P is known, which requires knowledge of the distri- bution of the primes in the interval I, then the conditional probability Pr(P | test is negative (cid:96) times) can be determined using Bayes’s rule. We do this in Section 5.4. Our Monte Carlo algorithm does not give a definite answer. However, if (cid:96) is large enough (say (cid:96) = 100), then the conditional probability that the number n being tested is prime given that the test is negative (cid:96) times, is very close to 1. 1.3 Some Tests for Compositeness The algorithms that we will discuss test three kinds of properties: (1) The Fermat test. For any odd integer n ≥ 5, pick randomly some a ∈ {2,...,n−2}, and test whether an−1 (cid:54)≡ 1 (mod n). If the test is positive, then return n is composite, else n is a “probable prime.” (2) The Miller–Rabin test. For any odd integer n ≥ 5, pick randomly some a ∈ {2,..., n−2}, and test whether (a) at (cid:54)≡ ±1 (mod n), and (b) a2it (cid:54)≡ n−1 (mod n), for all i with 1 ≤ i ≤ k −1. If the test is positive, then return n is composite, else n is a “probable prime.” (3) The Euler test. For any odd integer n ≥ 5, pick randomly some a ∈ {2,...,n − 2}, and test whether (cid:18) (cid:19) a a(n−1)/2 (cid:54)≡ 1 (mod n). n If the test is positive, then return n is composite, else n is a “probable prime.” The (cid:0) (cid:1) expression a is the Jacobi symbol. It is a generalization of the Legendre symbol. n These symbols have to do with quadratic residues. Given any integer n ≥ 2, an integer 10 CHAPTER 1. INTRODUCTION msuchthatgcd(m,n) = 1issaidtobeaquadratic residue mod n(orasquare mod n) if the congruence x2 ≡ m (mod n) (cid:0) (cid:1) has a solution. Let p be an odd prime. For any integer m, the Legendre symbol m is p defined as follows:  +1 if m is a quadratic residue modulo p (cid:18) (cid:19)  m  = −1 if m is a quadratic nonresidue modulo p p  0 if p divides m. (cid:0) (cid:1) The Jacobi symbol m is defined for a positive odd integer P ≥ 3 in terms of the P prime factorization of P; see Definition 6.3. The remarkable fact about the Legendre symbol is that it gives us an efficient method for testing whether a number m is a quadratic residue mod n without actually solving the congruence x2 ≡ m (mod n). The Jacobi symbol gives us an even more efficient method which avoids factoring. The reason is that there is an unexpected and deep relationship between the symbols (cid:0)p(cid:1) and (cid:0)q(cid:1), known as the law of quadratic reciprocity. q p The law of quadratic reciprocity was conjectured by Legendre and proved by Gauss, who gave no less than seven proofs. It is one of the gems of number theory, and we will prove it in Section 6.7. Property (1) of a Monte Carlo algorithm holds for all three tests. Next we need to show that Property (2) holds. For this, it is helpful to define the following sets of liars: for every odd composite n ≥ 3, LF = {a ∈ {1 ≤ a ≤ n−1} | an−1 ≡ 1 (mod n)}, n LMR = {a ∈ {1,...,n−1},either at ≡ 1 (mod n), n or a2it ≡ n−1 (mod n), for some i with 0 ≤ i ≤ k −1} (cid:18) (cid:19) a LE = {a ∈ {1,...,n} | a(n−1)/2 ≡ 1 (mod n)}. n n The set LF is called the set of F-liars (Fermat liars), the set LMR is called the set of n n MR-liars (Miller–Rabin liars) and the set LE is called the set of E-liars (Euler liars). n It is easy to see that all three sets of liars are subsets of the multiplicative group (Z/nZ)∗ of invertible elements of the ring Z/nZ. The order of this group is ϕ(n), a famous function due Euler, where ϕ(n) is the number of integers a with 1 ≤ a ≤ n such that gcd(a,n) = 1. Obviously, ϕ(n) < n if n > 1. Now if we could prove that our sets of liars are proper subsets of (Z/nZ)∗ of size at most ϕ(n)/2, then we woud be done, because the conditional probability that a is a liar given that n is composite would be at most ϕ(n)/(2n) < 1/2.