Chapter 2: Introduction to Number Theory PDF

1.10 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 1.3 1.4 1.5 1.6 1.7 1.8 1.9 45 Consider a financial report publishing system used to produce reports for various organizations. a. Give an example of a type of publication in which confidentiality of the stored data is the most important requirem...

1.10 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 1.3 1.4 1.5 1.6 1.7 1.8 1.9 45 Consider a financial report publishing system used to produce reports for various organizations. a. Give an example of a type of publication in which confidentiality of the stored data is the most important requirement. b. Give an example of a type of publication in which data integrity is the most important requirement. c. Give an example in which system availability is the most important requirement. For each of the following assets, assign a low, moderate, or high impact level for the loss of confidentiality, availability, and integrity, respectively. Justify your answers. a. A student maintaining a blog to post public information. b. An examination section of a university that is managing sensitive information about exam papers. c. An information system in a pathological laboratory maintaining the patient’s data. d. A student information system used for maintaining student data in a university that contains both personal, academic information and routine administrative information (not privacy related). Assess the impact for the two data sets separately and the information system as a whole. e. A University library contains a library management system which controls the distribution of books amongst the students of various departments. The library management system contains both the student data and the book data. Assess the impact for the two data sets separately and the information system as a whole. Draw a matrix similar to Table 1.4 that shows the relationship between security services and attacks. Draw a matrix similar to Table 1.4 that shows the relationship between security mechanisms and attacks. Develop an attack tree for gaining access to the contents of a physical safe. Consider a company whose operations are housed in two buildings on the same property; one building is headquarters, the other building contains network and computer services. The property is physically protected by a fence around the perimeter, and the only entrance to the property is through this fenced perimeter. In addition to the perimeter fence, physical security consists of a guarded front gate. The local networks are split between the Headquarters’ LAN and the Network Services’ LAN. Internet users connect to the Web server through a firewall. Dial-up users get access to a particular server on the Network Services’ LAN. Develop an attack tree in which the root node represents disclosure of proprietary secrets. Include physical, social engineering, and technical attacks. The tree may contain both AND and OR nodes. Develop a tree that has at least 15 leaf nodes. Read all of the classic papers cited in the Recommended Reading section for this chapter, available at the Author Web site at WilliamStallings.com/Cryptography. The papers are available at box.com/Crypto7e. Compose a 500–1000 word paper (or 8–12 slide PowerPoint presentation) that summarizes the key concepts that emerge from these papers, emphasizing concepts that are common to most or all of the papers. CHAPTER Introduction to Number Theory 2.1 Divisibility and The Division Algorithm Divisibility The Division Algorithm 2.2 The Euclidean Algorithm Greatest Common Divisor Finding the Greatest Common Divisor 2.3 Modular Arithmetic The Modulus Properties of Congruences Modular Arithmetic Operations Properties of Modular Arithmetic Euclidean Algorithm Revisited The Extended Euclidean Algorithm 2.4 Prime Numbers 2.5 Fermat’s and Euler’s Theorems Fermat’s Theorem Euler’s Totient Function Euler’s Theorem 2.6 Testing for Primality Miller–Rabin Algorithm A Deterministic Primality Algorithm Distribution of Primes 2.7 The Chinese Remainder Theorem 2.8 Discrete Logarithms The Powers of an Integer, Modulo n Logarithms for Modular Arithmetic Calculation of Discrete Logarithms 2.9 Key Terms, Review Questions, and Problems Appendix 2A The Meaning of Mod 46 Hiva-Network.Com 2.1 / DIVISIBILITY AND THE DIVISION ALGORITHM 47 LEARNING OBJECTIVES After studying this chapter, you should be able to: ◆ Understand the concept of divisibility and the division algorithm. ◆ Understand how to use the Euclidean algorithm to find the greatest common divisor. ◆ Present an overview of the concepts of modular arithmetic. ◆ Explain the operation of the extended Euclidean algorithm. ◆ Discuss key concepts relating to prime numbers. ◆ Understand Fermat’s theorem. ◆ Understand Euler’s theorem. ◆ Define Euler’s totient function. ◆ Make a presentation on the topic of testing for primality. ◆ Explain the Chinese remainder theorem. ◆ Define discrete logarithms. Number theory is pervasive in cryptographic algorithms. This chapter provides sufficient breadth and depth of coverage of relevant number theory topics for understanding the wide range of applications in cryptography. The reader familiar with these topics can safely skip this chapter. The first three sections introduce basic concepts from number theory that are needed for understanding finite fields; these include divisibility, the Euclidian algorithm, and modular arithmetic. The reader may study these sections now or wait until ready to tackle Chapter 5 on finite fields. Sections 2.4 through 2.8 discuss aspects of number theory related to prime numbers and discrete logarithms. These topics are fundamental to the design of asymmetric (public-key) cryptographic algorithms. The reader may study these sections now or wait until ready to read Part Three. The concepts and techniques of number theory are quite abstract, and it is often difficult to grasp them intuitively without examples. Accordingly, this chapter includes a number of examples, each of which is highlighted in a shaded box. 2.1 DIVISIBILITY AND THE DIVISION ALGORITHM Divisibility We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers. That is, b divides a if there is no remainder on division. The notation b  a is commonly used to mean b divides a. Also, if b  a, we say that b is a divisor of a. 48 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. 13 182; -5 30; 17 289; -3 33; 17 0 Subsequently, we will need some simple properties of divisibility for integers, which are as follows: ■ ■ ■ ■ If a 1, then a = {1. If a b and b  a, then a = {b. Any b ≠ 0 divides 0. If a b and b  c, then a c: 11 66 and 66 198 1 11 198 ■ If b  g and b  h, then b  (mg + nh) for arbitrary integers m and n. To see this last point, note that ■ ■ If b  g, then g is of the form g = b * g1 for some integer g1. If b  h, then h is of the form h = b * h1 for some integer h1. So mg + nh = mbg1 + nbh1 = b * (mg1 + nh1) and therefore b divides mg + nh. b = 7; g = 14; h = 63; m = 3; n = 2 7 14 and 7 63. To show 7 (3 * 14 + 2 * 63), we have (3 * 14 + 2 * 63) = 7(3 * 2 + 2 * 9), and it is obvious that 7 (7(3 * 2 + 2 * 9)). The Division Algorithm Given any positive integer n and any nonnegative integer a, if we divide a by n, we get an integer quotient q and an integer remainder r that obey the following relationship: a = qn + r 0 … r 6 n; q = : a/n ; (2.1) where : x ; is the largest integer less than or equal to x. Equation (2.1) is referred to as the division algorithm.1 1 Equation (2.1) expresses a theorem rather than an algorithm, but by tradition, this is referred to as the division algorithm. 2.2 / THE EUCLIDEAN ALGORITHM 49 n n 2n qn 3n a (q + 1)n 0 r (a) General relationship 15 0 15 30 = 2 × 15 45 = 3 × 15 60 = 4 × 15 (b) Example: 70 = (4 × 15) + 10 70 75 = 5 × 15 10 Figure 2.1 The Relationship a = qn + r; 0 … r 6 n Figure 2.1a demonstrates that, given a and positive n, it is always possible to find q and r that satisfy the preceding relationship. Represent the integers on the number line; a will fall somewhere on that line (positive a is shown, a similar demonstration can be made for negative a). Starting at 0, proceed to n, 2n, up to qn, such that qn … a and (q + 1)n 7 a. The distance from qn to a is r, and we have found the unique values of q and r. The remainder r is often referred to as a residue. a = 11; a = -11; n = 7; n = 7; 11 = 1 * 7 + 4; -11 = ( -2) * 7 + 3; r = 4 r = 3 q = 1 q = -2 Figure 2.1b provides another example. 2.2 THE EUCLIDEAN ALGORITHM One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers. First, we need a simple definition: Two integers are relatively prime if and only if their only common positive integer factor is 1. Greatest Common Divisor Recall that nonzero b is defined to be a divisor of a if a = mb for some m, where a, b, and m are integers. We will use the notation gcd(a, b) to mean the greatest common divisor of a and b. The greatest common divisor of a and b is the largest integer that divides both a and b. We also define gcd(0, 0) = 0. 50 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY More formally, the positive integer c is said to be the greatest common divisor of a and b if 1. c is a divisor of a and of b. 2. any divisor of a and b is a divisor of c. An equivalent definition is the following: gcd(a, b) = max[k, such that k a and k b] Because we require that the greatest common divisor be positive, gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b). In general, gcd(a, b) = gcd( a ,  b  ). gcd(60, 24) = gcd(60, -24) = 12 Also, because all nonzero integers divide 0, we have gcd(a, 0) =  a . We stated that two integers a and b are relatively prime if and only if their only common positive integer factor is 1. This is equivalent to saying that a and b are relatively prime if gcd(a, b) = 1. 8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 8, and the positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only integer on both lists. Finding the Greatest Common Divisor We now describe an algorithm credited to Euclid for easily finding the greatest common divisor of two integers (Figure 2.2). This algorithm has broad significance in cryptography. The explanation of the algorithm can be broken down into the following points: 1. Suppose we wish to determine the greatest common divisor d of the integers a and b; that is determine d = gcd(a, b). Because gcd(  a ,  b  ) = gcd(a, b), there is no harm in assuming a Ú b 7 0. 2. Dividing a by b and applying the division algorithm, we can state: a = q1b + r1 0 … r1 6 b (2.2) 3. First consider the case in which r1 = 0. Therefore b divides a and clearly no larger number divides both b and a, because that number would be larger than b. So we have d = gcd(a, b) = b. 4. The other possibility from Equation (2.2) is r1 ≠ 0. For this case, we can state that d  r1. This is due to the basic properties of divisibility: the relations d  a and d  b together imply that d  (a - q1b), which is the same as d  r1. 5. Before proceeding with the Euclidian algorithm, we need to answer the question: What is the gcd(b, r1)? We know that d  b and d  r1. Now take any arbitrary integer c that divides both b and r1. Therefore, c (q1b + r1) = a. Because c divides both a and b, we must have c … d, which is the greatest common divisor of a and b. Therefore d = gcd(b, r1). 2.2 / THE EUCLIDEAN ALGORITHM 51 START No a > b? Divide a by b, calling the remainder r Yes Replace b with r Same GCD No r > 0? Swap a and b GCD Replace a with b GCD 710 = 2 × 310 + 90 GCD is the final value of b 310 = 3 × 90 + 40 END Figure 2.3 Euclidean Algorithm Example: gcd(710, 310) 90 = 2 × 40 + 10 40 = 4 × 10 Figure 2.2 Euclidean Algorithm Let us now return to Equation (2.2) and assume that r1 ≠ 0. Because b 7 r1, we can divide b by r1 and apply the division algorithm to obtain: b = q2r1 + r2 0 … r2 6 r1 As before, if r2 = 0, then d = r1 and if r2 ≠ 0, then d = gcd(r1, r2). Note that the remainders form a descending series of nonnegative values and so must terminate when the remainder is zero. This happens, say, at the (n + 1)th stage where rn - 1 is divided by rn. The result is the following system of equations: a = q1b + r1 b = q2r1 + r2 r1 = q3r2 + r3 ~ ~ ~ rn - 2 = qnrn - 1 + rn rn - 1 = qn + 1rn + 0 d = gcd(a, b) = rn 0 6 r1 6 0 6 r2 6 0 6 r3 6 ~ ~ ~ 0 6 rn 6 b r1 r2 w (2.3) rn - 1 At each iteration, we have d = gcd(ri, ri + 1) until finally d = gcd(rn, 0) = rn. Thus, we can find the greatest common divisor of two integers by repetitive application of the division algorithm. This scheme is known as the Euclidean algorithm. Figure 2.3 illustrates a simple example. We have essentially argued from the top down that the final result is the gcd(a, b). We can also argue from the bottom up. The first step is to show that rn divides a and b. It follows from the last division in Equation (2.3) that rn divides rn - 1. The next to last division shows that rn divides rn - 2 because it divides both 52 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY terms on the right. Successively, one sees that rn divides all ri >s and finally a and b. It remains to show that rn is the largest divisor that divides a and b. If we take any arbitrary integer that divides a and b, it must also divide r1, as explained previously. We can follow the sequence of equations in Equation (2.3) down and show that c must divide all ri >s. Therefore c must divide rn, so that rn = gcd(a, b). Let us now look at an example with relatively large numbers to see the power of this algorithm: To find d = gcd(a, b) = gcd(1160718174, 316258250) a = q1b + r1 1160718174 = 3 * 316258250 + 211943424 d = gcd(316258250, 211943424) b = q2r1 + r2 316258250 = 1 * 211943424 + 104314826 d = gcd(211943424, 104314826) r1 = q3r2 + r3 211943424 = 2 * 104314826 + 3313772 d = gcd(104314826, 3313772) r2 = q4r3 + r4 104314826 = 31 * 3313772 + 1587894 d = gcd(3313772, 1587894) d = gcd(1587894, 137984) r3 = q5r4 + r5 3313772 = 2 * 1587894 + 137984 r4 = q6r5 + r6 1587894 = 11 * 137984 + 70070 d = gcd(137984, 70070) r5 = q7r6 + r7 137984 = 1 * 70070 + 67914 d = gcd(70070, 67914) r6 = q8r7 + r8 70070 = 1 * 67914 + 2156 d = gcd(67914, 2156) r7 = q9r8 + r9 67914 = 31 * 2156 + 1078 d = gcd(2156, 1078) 2156 = 2 * 1078 + 0 r8 = q10r9 + r10 d = gcd(1078, 0) = 1078 Therefore, d = gcd(1160718174, 316258250) = 1078 In this example, we begin by dividing 1160718174 by 316258250, which gives 3 with a remainder of 211943424. Next we take 316258250 and divide it by 211943424. The process continues until we get a remainder of 0, yielding a result of 1078. It will be helpful in what follows to recast the above computation in tabular form. For every step of the iteration, we have ri - 2 = qiri - 1 + ri, where ri - 2 is the dividend, ri - 1 is the divisor, qi is the quotient, and ri is the remainder. Table 2.1 summarizes the results. Table 2.1 Euclidean Algorithm Example Dividend Divisor Quotient Remainder a = 1160718174 b = 316258250 q1 = 3 r1 = 211943424 b = 316258250 r1 = 211943434 q2 = 1 r2 = 104314826 r1 = 211943424 r2 = 104314826 q3 = 2 r3 = 3313772 r2 = 104314826 r3 = 3313772 q4 = 31 r4 = 1587894 r3 = 3313772 r4 = 1587894 q5 = 2 r5 = 137984 r4 = 1587894 r5 = 137984 q6 = 11 r6 = 70070 r5 = 137984 r6 = 70070 q7 = 1 r7 = 67914 r6 = 70070 r7 = 67914 q8 = 1 r8 = 2156 r7 = 67914 r8 = 2156 q9 = 31 r9 = 1078 r8 = 2156 r9 = 1078 q10 = 2 r10 = 0 2.3 / MODULAR ARITHMETIC 53 2.3 MODULAR ARITHMETIC The Modulus If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n. The integer n is called the modulus. Thus, for any integer a, we can rewrite Equation (2.1) as follows: a = qn + r 0 … r 6 n; q = : a/n ; a = : a/n ; * n + (a mod n) 11 mod 7 = 4; -11 mod 7 = 3 Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n). This is written as a K b (mod n).2 73 K 4 (mod 23); 21 K -9 (mod 10) Note that if a K 0 (mod n), then n  a. Properties of Congruences Congruences have the following properties: 1. a K b (mod n) if n  (a - b). 2. a K b (mod n) implies b K a (mod n). 3. a K b (mod n) and b K c (mod n) imply a K c (mod n). To demonstrate the first point, if n  (a - b), then (a - b) = kn for some k. So we can write a = b + kn. Therefore, (a mod n) = (remainder when b + kn is divided by n) = (remainder when b is divided by n) = (b mod n). 23 K 8 (mod 5) -11 K 5 (mod 8) 81 K 0 (mod 27) because because because 23 - 8 = 15 = 5 * 3 -11 - 5 = -16 = 8 * ( -2) 81 - 0 = 81 = 27 * 3 The remaining points are as easily proved. 2 We have just used the operator mod in two different ways: first as a binary operator that produces a remainder, as in the expression a mod b; second as a congruence relation that shows the equivalence of two integers, as in the expression a K b (mod n). See Appendix 2A for a discussion. 54 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY Modular Arithmetic Operations Note that, by definition (Figure 2.1), the (mod n) operator maps all integers into the set of integers {0, 1, c , (n - 1)}. This suggests the question: Can we perform arithmetic operations within the confines of this set? It turns out that we can; this technique is known as modular arithmetic. Modular arithmetic exhibits the following properties: 1. [(a mod n) + (b mod n)] mod n = (a + b) mod n 2. [(a mod n) - (b mod n)] mod n = (a - b) mod n 3. [(a mod n) * (b mod n)] mod n = (a * b) mod n We demonstrate the first property. Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + jn for some integer j and b = rb + kn for some integer k. Then (a + b) mod n = = = = (ra + jn + rb + kn) mod n (ra + rb + (k + j)n) mod n (ra + rb) mod n [(a mod n) + (b mod n)] mod n The remaining properties are proven as easily. Here are examples of the three properties: 11 mod 8 = 3; 15 mod 8 = 7 [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15) mod 8 = 26 mod 8 = 2 [(11 mod 8) - (15 mod 8)] mod 8 = -4 mod 8 = 4 (11 - 15) mod 8 = -4 mod 8 = 4 [(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 * 15) mod 8 = 165 mod 8 = 5 Exponentiation is performed by repeated multiplication, as in ordinary arithmetic. To find 117 mod 13, we can proceed as follows: 112 = 121 K 4 (mod 13) 114 = (112)2 K 42 K 3 (mod 13) 117 = 11 * 112 * 114 117 K 11 * 4 * 3 K 132 K 2 (mod 13) Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into modular arithmetic. 2.3 / MODULAR ARITHMETIC 55 Table 2.2 provides an illustration of modular addition and multiplication modulo 8. Looking at addition, the results are straightforward, and there is a regular pattern to the matrix. Both matrices are symmetric about the main diagonal in conformance to the commutative property of addition and multiplication. As in ordinary addition, there is an additive inverse, or negative, to each integer in modular arithmetic. In this case, the negative of an integer x is the integer y such that (x + y) mod 8 = 0. To find the additive inverse of an integer in the left-hand column, scan across the corresponding row of the matrix to find the value 0; the integer at the top of that column is the additive inverse; thus, (2 + 6) mod 8 = 0. Similarly, the entries in the multiplication table are straightforward. In modular arithmetic mod 8, the multiplicative inverse of x is the integer y such that (x * y) mod 8 = 1 mod 8. Now, to find the multiplicative inverse of an integer from the multiplication table, scan across the matrix in the row for that integer to find the value 1; the integer at the top of that column is the multiplicative inverse; thus, (3 * 3) mod 8 = 1. Note that not all integers mod 8 have a multiplicative inverse; more about that later. Properties of Modular Arithmetic Define the set Z n as the set of nonnegative integers less than n: Z n = {0, 1, c , (n - 1)} Table 2.2 Arithmetic Modulo 8 + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6 (a) Addition modulo 8 * 0 1 2 3 4 5 6 7 w -w w -1 0 0 0 0 0 0 0 0 0 0 0 — 1 0 1 2 3 4 5 6 7 1 7 1 2 6 — 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 3 5 3 4 — 3 5 4 0 4 0 4 0 4 0 4 4 5 0 5 2 7 4 1 6 3 5 6 0 6 4 2 0 6 4 2 6 2 — 7 0 7 6 5 4 3 2 1 7 1 7 (b) Multiplication modulo 8 Hiva-Network.Com (c) Additive and multiplicative inverse modulo 8 56 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY This is referred to as the set of residues, or residue classes (mod n). To be more precise, each integer in Z n represents a residue class. We can label the residue classes (mod n) as [0], [1], [2], c , [n - 1], where [r] = {a: a is an integer, a K r (mod n)} The residue classes (mod 4) are [0] = { c , -16, -12, -8, -4, 0, 4, 8, 12, 16, c } [1] = { c , -15, -11, -7, -3, 1, 5, 9, 13, 17, c } [2] = { c , -14, -10, -6, -2, 2, 6, 10, 14, 18, c } [3] = { c , -13, -9, -5, -1, 3, 7, 11, 15, 19, c } Of all the integers in a residue class, the smallest nonnegative integer is the one used to represent the residue class. Finding the smallest nonnegative integer to which k is congruent modulo n is called reducing k modulo n. If we perform modular arithmetic within Z n, the properties shown in Table 2.3 hold for integers in Z n. We show in the next section that this implies that Z n is a commutative ring with a multiplicative identity element. There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe that (as in ordinary arithmetic) we can write the following: if (a + b) K (a + c) (mod n) then b K c (mod n) (2.4) (5 + 23) K (5 + 7)(mod 8); 23 K 7(mod 8) Equation (2.4) is consistent with the existence of an additive inverse. Adding the additive inverse of a to both sides of Equation (2.4), we have (( -a) + a + b) K (( -a) + a + c)(mod n) b K c (mod n) Table 2.3 Properties of Modular Arithmetic for Integers in Z n Property Expression Commutative Laws (w + x) mod n = (x + w) mod n (w * x) mod n = (x * w) mod n Associative Laws [(w + x) + y] mod n = [w + (x + y)] mod n [(w * x) * y] mod n = [w * (x * y)] mod n Distributive Law [w * (x + y)] mod n = [(w * x) + (w * y)] mod n Identities (0 + w) mod n = w mod n (1 * w) mod n = w mod n Additive Inverse ( - w) For each w ∈ Z n, there exists a z such that w + z K 0 mod n 2.3 / MODULAR ARITHMETIC 57 However, the following statement is true only with the attached condition: if (a * b) K (a * c)(mod n) then b K c(mod n) if a is relatively prime to n (2.5) Recall that two integers are relatively prime if their only common positive integer factor is 1. Similar to the case of Equation (2.4), we can say that Equation (2.5) is consistent with the existence of a multiplicative inverse. Applying the multiplicative inverse of a to both sides of Equation (2.5), we have ((a-1)ab) K ((a -1)ac)(mod n) b K c(mod n) To see this, consider an example in which the condition of Equation (2.5) does not hold. The integers 6 and 8 are not relatively prime, since they have the common factor 2. We have the following: 6 * 3 = 18 K 2(mod 8) 6 * 7 = 42 K 2(mod 8) Yet 3 [ 7 (mod 8). The reason for this strange result is that for any general modulus n, a multiplier a that is applied in turn to the integers 0 through (n - 1) will fail to produce a complete set of residues if a and n have any factors in common. With a = 6 and n = 8, Z8 Multiply by 6 Residues 0 0 0 1 2 6 12 6 4 3 18 2 4 24 0 5 30 6 6 36 4 7 42 2 Because we do not have a complete set of residues when multiplying by 6, more than one integer in Z 8 maps into the same residue. Specifically, 6 * 0 mod 8 = 6 * 4 mod 8; 6 * 1 mod 8 = 6 * 5 mod 8; and so on. Because this is a many-to-one mapping, there is not a unique inverse to the multiply operation. However, if we take a = 5 and n = 8, whose only common factor is 1, Z8 Multiply by 5 Residues 0 0 0 1 2 5 10 5 2 3 15 7 4 20 4 5 25 1 6 30 6 7 35 3 The line of residues contains all the integers in Z 8, in a different order. 58 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY In general, an integer has a multiplicative inverse in Z n if and only if that integer is relatively prime to n. Table 2.2c shows that the integers 1, 3, 5, and 7 have a multiplicative inverse in Z 8; but 2, 4, and 6 do not. Euclidean Algorithm Revisited The Euclidean algorithm can be based on the following theorem: For any integers a, b, with a Ú b Ú 0, gcd(a, b) = gcd(b, a mod b) (2.6) gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11 To see that Equation (2.6) works, let d = gcd(a, b). Then, by the definition of gcd, d  a and d  b. For any positive integer b, we can express a as a = kb + r K r (mod b) a mod b = r with k, r integers. Therefore, (a mod b) = a - kb for some integer k. But because d  b, it also divides kb. We also have d  a. Therefore, d  (a mod b). This shows that d is a common divisor of b and (a mod b). Conversely, if d is a common divisor of b and (a mod b), then d  kb and thus d  [kb + (a mod b)], which is equivalent to d  a. Thus, the set of common divisors of a and b is equal to the set of common divisors of b and (a mod b). Therefore, the gcd of one pair is the same as the gcd of the other pair, proving the theorem. Equation (2.6) can be used repetitively to determine the greatest common divisor. gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6 gcd(11, 10) = gcd(10, 1) = gcd(1, 0) = 1 This is the same scheme shown in Equation (2.3), which can be rewritten in the following way. Euclidean Algorithm Calculate Which satisfies r1 = a mod b a = q1b + r1 r2 = b mod r1 b = q2r1 + r2 r3 = r1 mod r2 ~ ~ ~ rn = rn - 2 mod rn - 1 r1 = q3r2 + r3 ~ ~ ~ rn - 2 = qnrn - 1 + rn rn + 1 = rn - 1 mod rn = 0 rn - 1 = qn + 1rn + 0 d = gcd(a, b) = rn We can define the Euclidean algorithm concisely as the following recursive function. 2.3 / MODULAR ARITHMETIC 59 Euclid(a,b) if (b=0) then return a; else return Euclid(b, a mod b); The Extended Euclidean Algorithm We now proceed to look at an extension to the Euclidean algorithm that will be important for later computations in the area of finite fields and in encryption algorithms, such as RSA. For given integers a and b, the extended Euclidean algorithm not only calculates the greatest common divisor d but also two additional integers x and y that satisfy the following equation. ax + by = d = gcd(a, b) (2.7) It should be clear that x and y will have opposite signs. Before examining the algorithm, let us look at some of the values of x and y when a = 42 and b = 30. Note that gcd(42, 30) = 6. Here is a partial table of values3 for 42x + 30y. x −3 −2 −1 0 1 2 3 y -3 -216 - 174 -132 -90 - 48 -6 36 -2 - 186 - 144 - 102 - 60 -18 24 66 -1 - 156 - 114 - 72 - 30 12 54 96 0 - 126 - 84 - 42 0 42 84 126 1 - 96 - 54 - 12 30 72 114 156 2 - 66 - 24 18 60 102 144 186 3 - 36 6 48 90 132 174 216 Observe that all of the entries are divisible by 6. This is not surprising, because both 42 and 30 are divisible by 6, so every number of the form 42x + 30y = 6(7x + 5y) is a multiple of 6. Note also that gcd(42, 30) = 6 appears in the table. In general, it can be shown that for given integers a and b, the smallest positive value of ax + by is equal to gcd(a, b). Now let us show how to extend the Euclidean algorithm to determine (x, y, d) given a and b. We again go through the sequence of divisions indicated in Equation (2.3), and we assume that at each step i we can find integers xi and yi that satisfy ri = axi + byi. We end up with the following sequence. a = q1b + r1 b = q2r1 + r2 r1 = q3r2 + r3 f rn - 2 = qnrn - 1 + rn rn - 1 = qn + 1rn + 0 3 This example is taken from [SILV06]. r1 = ax1 + r2 = ax2 + r3 = ax3 + f rn = axn + by1 by2 by3 byn 60 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY Now, observe that we can rearrange terms to write ri = ri - 2 - ri - 1qi (2.8) Also, in rows i - 1 and i - 2, we find the values ri - 2 = axi - 2 + byi - 2 and ri - 1 = axi - 1 + byi - 1 Substituting into Equation (2.8), we have ri = (axi - 2 + byi - 2) - (axi - 1 + byi - 1)qi = a(xi - 2 - qixi - 1) + b(yi - 2 - qiyi - 1) But we have already assumed that ri = axi + byi. Therefore, xi = xi - 2 - qixi - 1 and yi = yi - 2 - qiyi - 1 We now summarize the calculations: Extended Euclidean Algorithm Calculate Which satisfies Calculate Which satisfies r -1 = a x-1 = 1; y-1 = 0 a = ax-1 + by-1 r0 = b x0 = 0; y0 = 1 b = ax0 + by0 r1 = a mod b q1 = : a/b ; a = q1b + r1 x1 = x-1 - q1x0 = 1 r1 = ax1 + by1 y1 = y-1 - q1y0 = -q1 r2 = b mod r1 q2 = : b/r1 ; b = q2r1 + r2 x2 = x0 - q2x1 y2 = y0 - q2y1 r2 = ax2 + by2 r3 = r1 mod r2 q3 = : r1/r2 ; r1 = q3r2 + r3 x3 = x1 - q3x2 y3 = y1 - q3y2 r3 = ax3 + by3 ~ ~ ~ rn = rn - 2 mod rn - 1 qn = : rn - 2/rn - 1 ; ~ ~ ~ ~ ~ ~ rn - 2 = qnrn - 1 + rn xn = xn - 2 - qnxn - 1 yn = yn - 2 - qnyn - 1 rn + 1 = rn - 1 mod rn = 0 rn - 1 = qn + 1rn + 0 qn + 1 = : rn - 1/rn ; ~ ~ ~ rn = axn + byn d = gcd(a, b) = rn x = xn; y = yn We need to make several additional comments here. In each row, we calculate a new remainder ri based on the remainders of the previous two rows, namely ri - 1 and ri - 2. To start the algorithm, we need values for r0 and r-1, which are just a and b. It is then straightforward to determine the required values for x-1, y-1, x0, and y0. We know from the original Euclidean algorithm that the process ends with a remainder of zero and that the greatest common divisor of a and b is d = gcd(a, b) = rn. But we also have determined that d = rn = axn + byn. Therefore, in Equation (2.7), x = xn and y = yn. As an example, let us use a = 1759 and b = 550 and solve for 1759x + 550y = gcd(1759, 550). The results are shown in Table 2.4. Thus, we have 1759 * ( -111) + 550 * 355 = -195249 + 195250 = 1. 2.4 / PRIME NUMBERS Table 2.4 61 Extended Euclidean Algorithm Example i ri xi yi -1 1759 qi 1 0 0 550 0 1 1 109 3 1 -3 2 5 5 -5 16 3 4 21 106 - 339 4 1 1 - 111 355 5 0 4 Result: d = 1; x = - 111; y = 355 2.4 PRIME NUMBERS4 A central concern of number theory is the study of prime numbers. Indeed, whole books have been written on the subject (e.g., [CRAN01], [RIBE96]). In this section, we provide an overview relevant to the concerns of this book. An integer p 7 1 is a prime number if and only if its only divisors5 are {1 and {p. Prime numbers play a critical role in number theory and in the techniques discussed in this chapter. Table 2.5 shows the primes less than 2000. Note the way the primes are distributed. In particular, note the number of primes in each range of 100 numbers. Any integer a 7 1 can be factored in a unique way as a = pa11 * pa22 * g * pat t (2.9) where p1 6 p2 6 c 6 pt are prime numbers and where each ai is a positive integer. This is known as the fundamental theorem of arithmetic; a proof can be found in any text on number theory. 91 = 7 * 13 3600 = 24 * 32 * 52 11011 = 7 * 112 * 13 It is useful for what follows to express this another way. If P is the set of all prime numbers, then any positive integer a can be written uniquely in the following form: a = q pap where each ap Ú 0 p∈P 4 In this section, unless otherwise noted, we deal only with the nonnegative integers. The use of negative integers would introduce no essential differences. 5 Recall from Section 2.1 that integer a is said to be a divisor of integer b if there is no remainder on division. Equivalently, we say that a divides b. 229 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 97 89 83 79 227 107 5 293 283 281 277 271 269 263 257 251 241 239 233 223 103 3 211 101 397 389 383 379 373 367 359 353 349 347 337 331 317 313 311 307 499 491 487 479 467 463 461 457 449 443 439 433 431 421 419 409 401 Primes Under 2000 2 Table 2.5 599 593 587 577 571 569 563 557 547 541 523 521 509 503 691 683 677 673 661 659 653 647 643 641 631 619 617 613 607 601 797 787 773 769 761 757 751 743 739 733 727 719 709 701 887 883 881 877 863 859 857 853 839 829 827 823 821 811 809 997 991 983 977 971 967 953 947 941 937 929 919 911 907 1097 1093 1091 1087 1069 1063 1061 1051 1049 1039 1033 1031 1021 1019 1013 1009 1193 1187 1181 1171 1163 1153 1151 1129 1123 1117 1109 1103 1297 1291 1289 1283 1279 1277 1259 1249 1237 1231 1229 1223 1217 1213 1201 1399 1381 1373 1367 1361 1327 1321 1319 1307 1303 1301 1499 1493 1489 1487 1483 1481 1471 1459 1453 1451 1447 1439 1433 1429 1427 1423 1409 1597 1583 1579 1571 1567 1559 1553 1549 1543 1531 1523 1511 1699 1697 1693 1669 1667 1663 1657 1637 1627 1621 1619 1613 1609 1607 1601 1789 1787 1783 1777 1759 1753 1747 1741 1733 1723 1721 1709 1889 1879 1877 1873 1871 1867 1861 1847 1831 1823 1811 1801 1999 1997 1993 1987 1979 1973 1951 1949 1933 1931 1913 1907 1901 62 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY 2.4 / PRIME NUMBERS 63 The right-hand side is the product over all possible prime numbers p; for any particular value of a, most of the exponents ap will be 0. The value of any given positive integer can be specified by simply listing all the nonzero exponents in the foregoing formulation. The integer 12 is represented by {a2 = 2, a3 = 1}. The integer 18 is represented by {a2 = 1, a3 = 2}. The integer 91 is represented by {a7 = 1, a13 = 1}. Multiplication of two numbers is equivalent to adding the corresponding exponents. Given a = q pap, b = q pbp. Define k = ab. We know that the intep∈P p∈P ger k can be expressed as the product of powers of primes: k = q pkp. It follows p∈P that kp = ap + bp for all p ∈ P. k = 12 * 18 = (22 * 3) * (2 * 32) = 216 k2 = 2 + 1 = 3; k3 = 1 + 2 = 3 216 = 23 * 33 = 8 * 27 What does it mean, in terms of the prime factors of a and b, to say that a divides b? Any integer of the form pn can be divided only by an integer that is of a lesser or equal power of the same prime number, pj with j … n. Thus, we can say the following. Given a = q pap, b = q pbp p∈P p∈P If a b, then ap … bp for all p. a = 12; b = 36; 12 36 12 = 22 * 3; 36 = 22 * 32 a2 = 2 = b2 a3 = 1 … 2 = b3 Thus, the inequality ap … bp is satisfied for all prime numbers. It is easy to determine the greatest common divisor of two positive integers if we express each integer as the product of primes. 64 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY 300 = 22 * 31 * 52 18 = 21 * 32 gcd(18,300) = 21 * 31 * 50 = 6 The following relationship always holds: If k = gcd(a, b), then kp = min(ap, bp) for all p. Determining the prime factors of a large number is no easy task, so the preceding relationship does not directly lead to a practical method of calculating the greatest common divisor. 2.5 FERMAT’S AND EULER’S THEOREMS Two theorems that play important roles in public-key cryptography are Fermat’s theorem and Euler’s theorem. Fermat’s Theorem6 Fermat’s theorem states the following: If p is prime and a is a positive integer not divisible by p, then ap - 1 K 1 (mod p) (2.10) Proof: Consider the set of positive integers less than p: {1, 2, c , p - 1} and multiply each element by a, modulo p, to get the set X = {a mod p, 2a mod p, c , (p - 1)a mod p}. None of the elements of X is equal to zero because p does not divide a. Furthermore, no two of the integers in X are equal. To see this, assume that ja K ka(mod p)), where 1 … j 6 k … p - 1. Because a is relatively prime7 to p, we can eliminate a from both sides of the equation [see Equation (2.3)] resulting in j K k(mod p). This last equality is impossible, because j and k are both positive integers less than p. Therefore, we know that the (p - 1) elements of X are all positive integers with no two elements equal. We can conclude the X consists of the set of integers {1, 2, c , p - 1} in some order. Multiplying the numbers in both sets (p and X) and taking the result mod p yields a * 2a * g * (p - 1)a K [(1 * 2 * g * (p - 1)](mod p) ap - 1(p - 1)! K (p - 1)! (mod p) We can cancel the (p - 1)! term because it is relatively prime to p [see Equation (2.5)]. This yields Equation (2.10), which completes the proof. 6 This is sometimes referred to as Fermat’s little theorem. Recall from Section 2.2 that two numbers are relatively prime if they have no prime factors in common; that is, their only common divisor is 1. This is equivalent to saying that two numbers are relatively prime if their greatest common divisor is 1. 7 Hiva-Network.Com 2.5 / FERMAT’S AND EULER’S THEOREMS 65 a = 7, p = 19 72 = 49 K 11 (mod 19) 74 K 121 K 7 (mod 19) 78 K 49 K 11 (mod 19) 716 K 121 K 7 (mod 19) ap - 1 = 718 = 716 * 72 K 7 * 11 K 1 (mod 19) An alternative form of Fermat’s theorem is also useful: If p is prime and a is a positive integer, then ap K a(mod p) (2.11) Note that the first form of the theorem [Equation (2.10)] requires that a be relatively prime to p, but this form does not. p = 5, a = 3 p = 5, a = 10 ap = 35 = 243 K 3(mod 5) = a(mod p) ap = 105 = 100000 K 10(mod 5) K 0(mod 5) = a(mod p) Euler’s Totient Function Before presenting Euler’s theorem, we need to introduce an important quantity in number theory, referred to as Euler’s totient function. This function, written f(n), is defined as the number of positive integers less than n and relatively prime to n. By convention, f(1) = 1. Determine f(37) and f(35). Because 37 is prime, all of the positive integers from 1 through 36 are relatively prime to 37. Thus f(37) = 36. To determine f(35), we list all of the positive integers less than 35 that are relatively prime to it: 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34 There are 24 numbers on the list, so f(35) = 24. Table 2.6 lists the first 30 values of f(n). The value f(1) is without meaning but is defined to have the value 1. It should be clear that, for a prime number p, f(p) = p - 1 Now suppose that we have two prime numbers p and q with p ≠ q. Then we can show that, for n = pq, 66 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY Table 2.6 Some Values of Euler’s Totient Function f(n) n f(n) n f(n) n f(n) 1 1 11 10 21 12 2 1 12 4 22 10 3 2 13 12 23 22 4 2 14 6 24 8 5 4 15 8 25 20 6 2 16 8 26 12 7 6 17 16 27 18 8 4 18 6 28 12 9 6 19 18 29 28 10 4 20 8 30 8 f(n) = f(pq) = f(p) * f(q) = (p - 1) * (q - 1) To see that f(n) = f(p) * f(q), consider that the set of positive integers less than n is the set {1, c , (pq - 1)}. The integers in this set that are not relatively prime to n are the set {p, 2p, c , (q - 1)p} and the set {q, 2q, c , (p - 1)q}. To see this, consider that any integer that divides n must divide either of the prime numbers p or q. Therefore, any integer that does not contain either p or q as a factor is relatively prime to n. Further note that the two sets just listed are non-overlapping: Because p and q are prime, we can state that none of the integers in the first set can be written as a multiple of q, and none of the integers in the second set can be written as a multiple of p. Thus the total number of unique integers in the two sets is (q - 1) + (p - 1). Accordingly, f(n) = = = = (pq - 1) - [(q - 1) + (p - 1)] pq - (p + q) + 1 (p - 1) * (q - 1) f(p) * f(q) f(21) = f(3) * f(7) = (3 - 1) * (7 - 1) = 2 * 6 = 12 where the 12 integers are {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. Euler’s Theorem Euler’s theorem states that for every a and n that are relatively prime: af(n) K 1(mod n) (2.12) Proof: Equation (2.12) is true if n is prime, because in that case, f(n) = (n - 1) and Fermat’s theorem holds. However, it also holds for any integer n. Recall that 2.5 / FERMAT’S AND EULER’S THEOREMS 67 f(n) is the number of positive integers less than n that are relatively prime to n. Consider the set of such integers, labeled as R = {x1, x2, c , xf(n)} That is, each element xi of R is a unique positive integer less than n with gcd(xi, n) = 1. Now multiply each element by a, modulo n: S = {(ax1 mod n), (ax2 mod n), c , (axf(n) mod n)} The set S is a permutation8 of R , by the following line of reasoning: 1. Because a is relatively prime to n and xi is relatively prime to n, axi must also be relatively prime to n. Thus, all the members of S are integers that are less than n and that are relatively prime to n. 2. There are no duplicates in S. Refer to Equation (2.5). If axi mod n = axj mod n, then xi = xj. Therefore, f(n) f(n) q (axi mod n) = q xi i=1 f(n) i=1 f(n) i=1 f(n) i=1 f(n) i=1 i=1 q axi K q xi (mod n) af(n) * J q xi R K q xi (mod n) a f(n) K 1 (mod n) which completes the proof. This is the same line of reasoning applied to the proof of Fermat’s theorem. a = 3; n = 10; f(10) = 4; a = 2; n = 11; f(11) = 10; af(n) = 34 = 81 = 1(mod 10) = 1(mod n) af(n) = 210 = 1024 = 1(mod 11) = 1(mod n) As is the case for Fermat’s theorem, an alternative form of the theorem is also useful: af(n) + 1 K a(mod n) (2.13) Again, similar to the case with Fermat’s theorem, the first form of Euler’s theorem [Equation (2.12)] requires that a be relatively prime to n, but this form does not. 8 A permutation of a finite set of elements S is an ordered sequence of all the elements of S, with each element appearing exactly once. 68 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY 2.6 TESTING FOR PRIMALITY For many cryptographic algorithms, it is necessary to select one or more very large prime numbers at random. Thus, we are faced with the task of determining whether a given large number is prime. There is no simple yet efficient means of accomplishing this task. In this section, we present one attractive and popular algorithm. You may be surprised to learn that this algorithm yields a number that is not necessarily a prime. However, the algorithm can yield a number that is almost certainly a prime. This will be explained presently. We also make reference to a deterministic algorithm for finding primes. The section closes with a discussion concerning the distribution of primes. Miller–Rabin Algorithm9 The algorithm due to Miller and Rabin [MILL75, RABI80] is typically used to test a large number for primality. Before explaining the algorithm, we need some background. First, any positive odd integer n Ú 3 can be expressed as n - 1 = 2kq with k 7 0, q odd To see this, note that n - 1 is an even integer. Then, divide (n - 1) by 2 until the result is an odd number q, for a total of k divisions. If n is expressed as a binary number, then the result is achieved by shifting the number to the right until the rightmost digit is a 1, for a total of k shifts. We now develop two properties of prime numbers that we will need. TWO PROPERTIES OF PRIME NUMBERS The first property is stated as follows: If p is prime and a is a positive integer less than p, then a2 mod p = 1 if and only if either a mod p = 1 or a mod p = -1 mod p = p - 1. By the rules of modular arithmetic (a mod p) (a mod p) = a2 mod p. Thus, if either a mod p = 1 or a mod p = -1, then a2 mod p = 1. Conversely, if a2 mod p = 1, then (a mod p)2 = 1, which is true only for a mod p = 1 or a mod p = -1. The second property is stated as follows: Let p be a prime number greater than 2. We can then write p - 1 = 2kq with k 7 0, q odd. Let a be any integer in the range 1 6 a 6 p - 1. Then one of the two following conditions is true. 1. aq is congruent to 1 modulo p. That is, aq mod p = 1, or equivalently, aq K 1(mod p). k-1 2. One of the numbers aq, a2q, a4q, c , a2 q is congruent to -1 modulo p. That is, there is some number j in the range (1 … j … k) such that j-1 j-1 a2 q mod p = -1 mod p = p - 1 or equivalently, a2 q K - 1(mod p). Proof: Fermat’s theorem [Equation (2.10)] states that an - 1 K 1(mod n) if n is k prime. We have p - 1 = 2kq. Thus, we know that ap - 1 mod p = a2 q mod p = 1. Thus, if we look at the sequence of numbers aq mod p, a2q mod p, a4q mod p, c , a2 9 k-1 q k mod p, a2 q mod p (2.14) Also referred to in the literature as the Rabin-Miller algorithm, or the Rabin-Miller test, or the Miller– Rabin test. 2.6 / TESTING FOR PRIMALITY 69 we know that the last number in the list has value 1. Further, each number in the list is the square of the previous number. Therefore, one of the following possibilities must be true. 1. The first number on the list, and therefore all subsequent numbers on the list, equals 1. 2. Some number on the list does not equal 1, but its square mod p does equal 1. By virtue of the first property of prime numbers defined above, we know that the only number that satisfies this condition is p - 1. So, in this case, the list contains an element equal to p - 1. This completes the proof. DETAILS OF THE ALGORITHM These considerations lead to the conclusion that, if n is prime, then either the first element in the list of residues, or remainders, k-1 k (aq, a2q, c , a2 q, a2 q) modulo n equals 1; or some element in the list equals (n - 1); otherwise n is composite (i.e., not a prime). On the other hand, if the condition is met, that does not necessarily mean that n is prime. For example, if n = 2047 = 23 * 89, then n - 1 = 2 * 1023. We compute 21023 mod 2047 = 1, so that 2047 meets the condition but is not prime. We can use the preceding property to devise a test for primality. The procedure TEST takes a candidate integer n as input and returns the result composite if n is definitely not a prime, and the result inconclusive if n may or may not be a prime. TEST (n) 1. Find integers k, q, with k > 0, q odd, so that (n − 1 = 2k q); 2. Select a random integer a, 1 < a < n - 1; 3. if aq mod n = 1 then return(”inconclusive”); 4. for j = 0 to k - 1 do j 5. if a2 qmod n = n - 1 then return(”inconclusive”); 6. return(”composite”); Let us apply the test to the prime number n = 29. We have (n - 1) = 28 = 22(7) = 2kq. First, let us try a = 10. We compute 107 mod 29 = 17, which is neither 1 nor 28, so we continue the test. The next calculation finds that (107)2 mod 29 = 28, and the test returns inconclusive (i.e., 29 may be prime). Let’s try again with a = 2. We have the following calculations: 27 mod 29 = 12; 214 mod 29 = 28; and the test again returns inconclusive. If we perform the test for all integers a in the range 1 through 28, we get the same inconclusive result, which is compatible with n being a prime number. Now let us apply the test to the composite number n = 13 * 17 = 221. Then (n - 1) = 220 = 22(55) = 2kq. Let us try a = 5. Then we have 555 mod 221 = 112, which is neither 1 nor 220(555)2 mod 221 = 168. Because we have used all values of j (i.e., j = 0 and j = 1) in line 4 of the TEST algorithm, the test returns composite, indicating that 221 is definitely a composite number. But suppose we had selected a = 21. Then we have 2155 mod 221 = 200; (2155)2 mod 221 = 220; and the test returns inconclusive, indicating that 221 may be prime. In fact, of the 218 integers from 2 through 219, four of these will return an inconclusive result, namely 21, 47, 174, and 200. 70 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY REPEATED USE OF THE MILLER–RABIN ALGORITHM How can we use the Miller–Rabin algorithm to determine with a high degree of confidence whether or not an integer is prime? It can be shown [KNUT98] that given an odd number n that is not prime and a randomly chosen integer, a with 1 6 a 6 n - 1, the probability that TEST will return inconclusive (i.e., fail to detect that n is not prime) is less than 1/4. Thus, if t different values of a are chosen, the probability that all of them will pass TEST (return inconclusive) for n is less than (1/4)t. For example, for t = 10, the probability that a nonprime number will pass all ten tests is less than 10-6. Thus, for a sufficiently large value of t , we can be confident that n is prime if Miller’s test always returns inconclusive. This gives us a basis for determining whether an odd integer n is prime with a reasonable degree of confidence. The procedure is as follows: Repeatedly invoke TEST (n) using randomly chosen values for a. If, at any point, TEST returns composite, then n is determined to be nonprime. If TEST continues to return inconclusive for t tests, then for a sufficiently large value of t, assume that n is prime. A Deterministic Primality Algorithm Prior to 2002, there was no known method of efficiently proving the primality of very large numbers. All of the algorithms in use, including the most popular (Miller– Rabin), produced a probabilistic result. In 2002 (announced in 2002, published in 2004), Agrawal, Kayal, and Saxena [AGRA04] developed a relatively simple deterministic algorithm that efficiently determines whether a given large number is a prime. The algorithm, known as the AKS algorithm, does not appear to be as efficient as the Miller–Rabin algorithm. Thus far, it has not supplanted this older, probabilistic technique. Distribution of Primes It is worth noting how many numbers are likely to be rejected before a prime number is found using the Miller–Rabin test, or any other test for primality. A result from number theory, known as the prime number theorem, states that the primes near n are spaced on the average one every ln (n) integers. Thus, on average, one would have to test on the order of ln(n) integers before a prime is found. Because all even integers can be immediately rejected, the correct figure is 0.5 ln(n). For example, if a prime on the order of magnitude of 2200 were sought, then about 0.5 ln(2200) = 69 trials would be needed to find a prime. However, this figure is just an average. In some places along the number line, primes are closely packed, and in other places there are large gaps. The two consecutive odd integers 1,000,000,000,061 and 1,000,000,000,063 are both prime. On the other hand, 1001! + 2, 1001! + 3, c , 1001! + 1000, 1001! + 1001 is a sequence of 1000 consecutive composite integers. 2.7 / THE CHINESE REMAINDER THEOREM 71 2.7 THE CHINESE REMAINDER THEOREM One of the most useful results of number theory is the Chinese remainder theorem (CRT).10 In essence, the CRT says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli. The 10 integers in Z 10, that is the integers 0 through 9, can be reconstructed from their two residues modulo 2 and 5 (the relatively prime factors of 10). Say the known residues of a decimal digit x are r2 = 0 and r5 = 3; that is, x mod 2 = 0 and x mod 5 = 3. Therefore, x is an even integer in Z 10 whose remainder, on division by 5, is 3. The unique solution is x = 8. The CRT can be stated in several ways. We present here a formulation that is most useful from the point of view of this text. An alternative formulation is explored in Problem 2.33. Let k M = q mi i=1 where the mi are pairwise relatively prime; that is, gcd(mi, mj) = 1 for 1 … i, j … k, and i ≠ j. We can represent any integer A in Z M by a k-tuple whose elements are in Z mi using the following correspondence: A 4 (a1, a2, c , ak) (2.15) where A ∈ Z M, ai ∈ Z mi, and ai = A mod mi for 1 … i … k. The CRT makes two assertions. 1. The mapping of Equation (2.15) is a one-to-one correspondence (called a bijection) between Z M and the Cartesian product Z m1 * Z m2 * c * Z mk. That is, for every integer A such that 0 … A 6 M, there is a unique k-tuple (a1, a2, c , ak) with 0 … ai 6 mi that represents it, and for every such k-tuple (a1, a2, c , ak), there is a unique integer A in Z M. 2. Operations performed on the elements of Z M can be equivalently performed on the corresponding k-tuples by performing the operation independently in each coordinate position in the appropriate system. Let us demonstrate the first assertion. The transformation from A to (a1, a2, c , ak), is obviously unique; that is, each ai is uniquely calculated as ai = A mod mi. Computing A from (a1, a2, c , ak) can be done as follows. Let 10 The CRT is so called because it is believed to have been discovered by the Chinese mathematician Sun-Tsu in around 100 A.D. 72 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY Mi = M/mi for 1 … i … k. Note that Mi = m1 * m2 * c * mi - 1 * mi + 1 * c * mk, so that Mi K 0 (mod mj) for all j ≠ i. Then let ci = Mi * (Mi-1 mod mi) for 1 … i … k (2.16) By the definition of Mi, it is relatively prime to mi and therefore has a unique multiplicative inverse mod mi. So Equation (2.16) is well defined and produces a unique value ci. We can now compute k A K ¢ a aici ≤(mod M) i=1 (2.17) To show that the value of A produced by Equation (2.17) is correct, we must show that ai = A mod mi for 1 … i … k. Note that cj K Mj K 0 (mod mi) if j ≠ i, and that ci K 1 (mod mi). It follows that ai = A mod mi. The second assertion of the CRT, concerning arithmetic operations, follows from the rules for modular arithmetic. That is, the second assertion can be stated as follows: If A 4 (a1, a2, c , ak) B 4 (b1, b2, c , bk) then (A + B) mod M 4 ((a1 + b1) mod m1, c , (ak + bk) mod mk) (A - B) mod M 4 ((a1 - b1) mod m1, c , (ak - bk) mod mk) (A * B) mod M 4 ((a1 * b1) mod m1, c , (ak * bk) mod mk) One of the useful features of the Chinese remainder theorem is that it provides a way to manipulate (potentially very large) numbers mod M in terms of tuples of smaller numbers. This can be useful when M is 150 digits or more. However, note that it is necessary to know beforehand the factorization of M. To represent 973 mod 1813 as a pair of numbers mod 37 and 49, define m1 m2 M A = = = = 37 49 1813 973 We also have M1 = 49 and M2 = 37. Using the extended Euclidean algorithm, we compute M1-1 = 34 mod m1 and M2-1 = 4 mod m2. (Note that we only need to compute each Mi and each Mi-1 once.) Taking residues modulo 37 and 49, our representation of 973 is (11, 42), because 973 mod 37 = 11 and 973 mod 49 = 42. Now suppose we want to add 678 to 973. What do we do to (11, 42)? First we compute (678) 4 (678 mod 37, 678 mod 49) = (12, 41). Then we add the tuples element-wise and reduce (11 + 12 mod 37, 42 + 41 mod 49) = (23, 34). To verify that this has the correct effect, we compute 2.8 / DISCRETE LOGARITHMS 73 (23, 34) 4 a1M1M1-1 + a2M2M2-1 mod M = [(23)(49)(34) + (34)(37)(4)] mod 1813 = 43350 mod 1813 = 1651 and check that it is equal to (973 + 678) mod 1813 = 1651. Remember that in the above derivation, Mi-1 is the multiplicative inverse of M1 modulo m1 and M2-1 is the multiplicative inverse of M2 modulo m2. Suppose we want to multiply 1651 (mod 1813) by 73. We multiply (23, 34) by 73 and reduce to get (23 * 73 mod 37, 34 * 73 mod 49) = (14, 32). It is easily verified that (14, 32) 4 [(14)(49)(34) + (32)(37)(4)] mod 1813 = 865 = 1651 * 73 mod 1813 2.8 DISCRETE LOGARITHMS Discrete logarithms are fundamental to a number of public-key algorithms, including Diffie–Hellman key exchange and the digital signature algorithm (DSA). This section provides a brief overview of discrete logarithms. For the interested reader, more detailed developments of this topic can be found in [ORE67] and [LEVE90]. The Powers of an Integer, Modulo n Recall from Euler’s theorem [Equation (2.12)] that, for every a and n that are relatively prime, af(n) K 1 (mod n) where f(n), Euler’s totient function, is the number of positive integers less than n and relatively prime to n. Now consider the more general expression: am K 1 (mod n) (2.18) If a and n are relatively prime, then there is at least one integer m that satisfies Equation (2.18), namely, m = f(n). The least positive exponent m for which Equation (2.18) holds is referred to in several ways: ■ ■ ■ The order of a (mod n) The exponent to which a belongs (mod n) The length of the period generated by a Hiva-Network.Com 74 CHAPTER 2 / INTRODUCTION TO NUMBER THEORY To see this last point, consider the powers of 7, modulo 19: 71 72 73 74 75 K = = = = 49 = 2 * 19 + 11 343 = 18 * 19 + 1 2401 = 126 * 19 + 7 16807 = 884 * 19 + 11 K K K K 7 (mod 19) 11 (mod 19) 1 (mod 19) 7 (mod 19) 11 (mod 19) There is no point in continuing because the sequence is repeating. This can be proven by noting that 73 K 1(mod 19), and therefore, 73 + j K 737j K 7j(mod 19), and hence, any two powers of 7 whose exponents differ by 3 (or a multiple of 3) are congruent to each other (mod 19). In other words, the sequence is periodic, and the length of the period is the smallest positive exponent m such that 7m K 1(mod 19). Table 2.7 shows all the powers of a, modulo 19 for all positive a 6 19. The length of the sequence for each base value is indicated by shading. Note the following: 1. All sequences end in 1. This is consistent with the reasoning of the preceding few paragraphs. 2. The length of a sequence divides f(19) = 18. That is, an integral number of sequences occur in each row of the table. 3. Some of the sequences are of length 18. In this case, it is said that the base integer a generates (via powers) the set of nonzero integers modulo 19. Each such integer is called a primitive root of the modulus 19. More generally, we can say that the highest possible exponent to which a number can belong (mod n) is f(n). If a number is of this order, it is referred to as a primitive root of n. The importance of this notion is that if a is a primitive root of n, then its powers a, a2, c , af(n) are distinct (mod n) and are all relatively prime to n. In particular, for a prime number p, if a is a primitive root of p, then a, a2, c , ap - 1 are distinct (mod p). For the prime number 19, its primitive roots are 2, 3, 10, 13, 14, and 15. Not all integers have primitive roots. In fact, the only integers with primitive roots are those of the form 2, 4, pa, and 2pa, where p is any odd prime and a is a positive integer. The proof is not simple but can be found in many number theory books, including [ORE76]. 2.8 / DISCRETE LOGARITHMS Table 2.7 75 Powers of Integers, Modulo 19 a a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5 1 5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4 1 6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12 1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 12 11 18 7 8 1 12 11 18 7 8 1 12 11 18 7 8 1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 1 16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6 1 17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 Logarithms for Modular Arithmetic With ordinary positive real numbers, the logarithm function is the inverse of exponentiatio