CS 15-451 Analysis of Algorithms 13 November 2003 Manuel & Avrim Blum Today: number theoretic algorithms, randomizing algorithms, and... QUIZ! 1. Let a, e, m be three n-bit numbers. Then can compute a^e mod m in O(n^3) steps using ordinary multiplication. More generally, can compute it in O(n*M(n)) steps using any fast integer multiplication that multiplies 2 n-bit numbers in M(n) steps. In what follows, we use n to denote the length of an input, and N to denote the positive input integer under consideration. 2. Observation 1 above has many applications, including the design of collision-resistant hash functions. pseudo-random generators, and Fast Randomizing Primality Tests. The latter tests are based on the following observation: Odd N = 3 5 7 9 11 13 15 17 19 21 2^(N-1) mod N = 1 1 1 4 1 1 4 1 1 4 Prime = 1 1 1 0 1 1 0 1 1 0 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 1 16 13 1 1 4 9 1 4 1 1 31 1 15 4 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 1 49 4 1 1 4 16 1 4 1 1 34 9 1 40 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 1 16 4 1 64 4 54 1 58 1 1 46 1 1 4 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 The above suggests (but naturally does not prove) the following FALSE assertion: Let N be an odd positive integer. Then: N prime <=> 2^(N-1) mod N = 1. Would that the assertion were true -- it would give us a fast primality test. (What would that test be?) The first counterexample is 341 = 11*31: 341 1 0 341 is called a 2-pseudo-prime. Fortunately, while 341 is a 2-pseudo-prime (2^340 mod 341 = 1) it is not a 3-pseudo-prime, since 3^340 mod 341 = 56 <> 1. So there is hope. In fact, if there is any integer a such that a^(N-1) mod N <> 1, then it follows from group theory that for at least half the integers x in the set {1,2,...,N-1}, x^(N-1) mod N <> 1. Before going on, here is what is true of the above (false) assertion: FERMAT'S LITTLE THEOREM: Let N be an odd positive integer. Let a be a positive integer less than N. Then: N prime => a^(N-1) mod N = 1. :( Note that the above implication goes in only one direction.) PROOF of Fermat's Little Theorem for the special case a=2: For N = P an odd prime: (1+1)^P = 1^P + (P choose 1)*1^(P-1) + (P choose 2)*1^(P-2) + ... + (P choose P)*1^(P-P). Therefore, 2^P mod P = (1+1)^P mod P = (1^P + (P choose P)*1^0) mod P = (1 + 1) mod P = 2. Since 2 is relatively prime to P, it has an inverse mod P. Multiplying both sides by this inverse gives 2^(P-1) mod P = 1. This proof for a=2 can be extended by induction to the general case of 0 < a < P. QED Recall the definition of a GROUP G: it is a set that is closed under an associative "multiplication" operation *, such that: 1. G contains an identity element 1: 1 satisfies 1*a = a*1 = a for all a in G, and 2. Every a in G has an inverse (a^-1) such that a*(a^-1) = (a^-1)*a = 1. A subgroup H of G is a subset of G that forms a group under the (same) operation *. THEOREM: Let H be a subgroup of a finite group G. Then |H| divides |G|. In other words, the number of elements in H divides the number of elements in G. It follows that if G has even one element that is not in H, then H contains at most half the elements of G. In what follows, G = Z* sub N denotes the group of all positive integers that are less than and relatively prime to N, under multiplication mod N. H = subgroup of G consisting of all elements a of G such that a^(N-1) mod N = 1. (You should check that H is a group!) This leads us to an *improved* but unfortunately still incorrect suggestion for a randomizing test for Primality. Randomizing algorithms: Generic randomizing algorithm: INPUT: 1. an urn containing either: 1.1 all white balls, or 1.2 an equal number of black and white balls, and 2. a positive integer k. OUTPUT: if the urn contains all white balls, then definitely output PROBABLY ALL WHITE; if the urn contains equal numbers of black and white, then probably output HALF WHITE HALf BLACK. Probability of error is at most 1/2^k. begin Do k times: Select a ball at random. If the ball is black, return HALF WHITE HALf BLACK. od return PROBABLY ALL WHITE end Example: Let N be a positive integer. Let Z* sub N denote the group of all positive integers that are less than and relatively prime to N, under multiplication mod N. THEOREM: Z* sub N contains phi(N) elements, where phi(p) = p-1 for any prime p, phi(p^k) = (p-1)*p^(k-1), and phi(p1^k1 * ... * pi^ki) = phi(p1^k1)*...*phi(pi^ki). It follows that if Z* sub N contains any element a such that a^(N-1) mod N <> 1, then at least half the elements of Z* sub N satisfy a^(N-1) mod N <> 1. (Why?) EXAMPLE: Let N = 15. Z* sub N = {1,2,4,7,8,11,13,14}. phi(15) = phi(3)*phi(5) = 2*4 = 8, and so |Z* sub N| = phi(N) = 8. The subgroup H of Z* sub N consisting of all elements a of Z* sub N such that a^(N-1) mod N = 1 is H = {1,4,11,15}. Z* sub N is the urn containing all white balls or at most half white balls. A ball a is white iff a^(N-1) mod N = 1. This suggests an improved randomizing algorithm for primality. What is it? Unfortunately, even this does not work. There are numbers called pseudo-primes or Carmichael numbers: these are composite numbers for which a^(N-1) mod N = 1 for all a in the range {1, 2, ..., N-1}. Indeed, there exist infinitely many Carmichael numbers. A lot is known about them. For example, such numbers are all products of three distinct primes. ASIDE: 1729 = The Hardy-Ramanujan "Taxi" number is Carmichael number: = 7*13*19 = least number expressible as sum of two positive integral cubes in two different ways: 1729 = 9^3+10^3 = 1^3+12^3 Fortunately, there is an efficient test for Carmichael numbers, so modulo this test, we have an efficient randomizing test for primality. Let pi(N) = number of primes less than N. Then pi(N) is asymptotic to N/(ln N), meaning that the ratio / pi(N) \ lim < --------- > = 1 N -> infinity \ N/(ln N) / Typical notation: pi(N) ~ N/ln(N). Application: Efficient generation of random n-bit primes.