8.3. Testing for PrimalityFor 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 Algorithm[6]
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 follows: n 1 = 2kq with k > 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 NumbersThe 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 mode p = p 1. By the rules of modular arithmetic (a mode p) (a mode p) = a2 mod p. Thus if either a mode 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 > 0 q odd. Let a be any integer in the range 1 < a < p 1. Then one of the two following conditions is true:
Details of the AlgorithmThese considerations lead to the conclusion that if n is prime, then either the first element in the list of residues, or remainders, (aq, a2q,..., a2k-1q, a2kq) 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 x 89, then n 1 = 2 x 1023. Computing, 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 = 2kq); 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 5. if a2jq mod n then return("inconclusive"); 6. return("composite");
Repeated Use of the Miller-Rabin AlgorithmHow 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 < a < 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 106. 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, for a sufficiently large value of t, assume that n is prime. A Deterministic Primality AlgorithmPrior 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, Agrawal, Kayal, and Saxena [AGRA02] 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 [BORN03]. Distribution of PrimesIt 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.
|