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 Algorithm
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
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 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:
-
aq is congruent to 1
modulo
p. That is,
aq mod
p = 1,
or equivalently,
aq ![]()
1 (mod
p).
-
One of the numbers
aq,
a2q,
a4q,...,
a2k-1q is congruent to 1 modulo
p. That is, there is some number
j in the range (1
![]()
j ![]()
k) such that
a2j-1q mod
p = 1 mod
p =
p 1, or equivalently,
a2j-1q ![]()
1 (mod
p).
Proof: Fermat's theorem [
Equation (8.2)] states that
an1
![]()
1 (mod
n)
if
n is prime. We have
p 1 = 2
kq. Thus, we know that
ap1 mod
p =
a2kq mod
p = 1. Thus, if we look at the sequence of
numbers
Equation 8-6
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:
-
The first number on the list, and therefore all subsequent
numbers on the list, equals 1.
-
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 p 1 is 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, (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 ![]()
n 1 then return("inconclusive");
6. return("composite");
Let us apply the
test to the prime number n = 29. We have ( n 1) = 28 = 2 2(7) = 2 kq. First, let us
try a = 10. We compute 10 7 mod 29 =
17, which is neither 1 nor 28, so we continue the test. The next calculation
finds that (10 7) 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: 2 7 mod 29 = 12;2 14 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
x 17 = 221. Then ( n 1) = 220 = 2 2(55)
= 2 kq.
Let us try a = 5. Then we have 5 55 mod
221 = 112, which is neither 1 nor 220; (5 55) 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 21 55 mod 221 = 200; (21 55) 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. |
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 <
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 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, 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, 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 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 2
200 were sought, then about 0.5
ln(2
200) = 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,...,
1001! + 1000, 1001! + 1001 is a sequence of 1000 consecutive composite
integers.
|
