Prime Generation & Testing for Primality

As discussed in cryptography, the ability to generate large prime numbers has become quite important in computer science. As it turns out, prime numbers are relatively easy to find if one has a means of testing for primality.

Testing the primality of a number n is done by searching for witnesses, numbers which prove that n is composite. If a witness is found, then n can not be prime and the test is finished. If, however, a sufficient amount of time passes and no witnesses are found, then the likelihood that n is prime is extremely good. Michael O. Rabin has defined a witness to the compositeness of n to be any integer w that satisfies the folling conditions:

  1. w^(n-1) = 1 mod n
  2. For some integer k, 1 < gcd(w^((n-1)/2^k) - 1, n) < n

So, how many times must we check for witnesses in order to prove that a number is prime? Below is a graph showing the distribution of witnesses. Except for the prime numbers for which there are no witnesses of compositeness, almost every composite number has a high percentage of witnesses.

This data is in keeping with Rabin's theorem:

If n is a composite number, then more than half the numbers in the set {2, 3, . . . , n - 1) are witnesses to the compositeness of n.

Testing numbers for primality is therefore an implementation of the Monte Carlo method discussed elsewhere on this site. It relies on a random sampling of numbers that could be factors. The algorithm needed to test for primality must therefore follow the following steps:

  1. Input n.
  2. Select m integers w1, w2, . . . , wm at random from the set (2, 3, . . . , n + 1).
  3. For i = 1, 2, . . . , m, test whether wi is a witness.
  4. If none of the m integers are witnesses, output yes, else, ouput no.

Therefore, since at least half of all the integers in the set between 1 and n are witnesses, the probability that n is prime is at least 1 - (1/2)^m. Thus, a reasonable m value can achieve a high rate of accuracy.

 

The chart and much of the information on Cryptography and Prime Number Generation were obtained from the work of Rajiv Gupta, Scott A. Smolka and Shaji Bhaskar. For more information, see page 19-22 of their article "On Randomization in Sequential and Distributed Algorithms". Additionally, M. O. Rabin's theories and ideas printed in the section "Detecting Primes" in The Turing Omnibus were of great help.

Back to Applications Main Page