Prime Numbers

An integer p > 1 is called a prime number, or a prime, in case there is no divisor d of p satisfying 1 < d < p. If an integer a > 1 is not a prime, it is called a composite number.

Some characteristics of primes

Every integer n greater than 1 can be expressed as a product of primes (with perhaps only one factor)
There are arbitrarily large gaps in the series of primes
The number of primes is infinite. That is, there is no end to the sequence of primes
The factoring of any integer n > 1 into primes is unique apart from the order of the prime factors
If p is a prime then (p - 1)! = -1 mod p. (Wilson’s Theorem)

The RSA cryptographic algorithm uses a lot of prime numbers in generating its keys. These keys in turn will hold the strength of the encryption.

Public-key algorithms need prime numbers. Any reasonably sized network needs lots of them. Before discussing the mathematics of prime number generation, we will answer a few obvious questions.

If everyone needs a different prime number, won’t we run out? No. In fact, there are approximately 10¹⁵¹ primes 512-bits in length or less. For numbers near n, the probability that a random number is prime is approximately one in ln n. So the total number of primes less that n is n/(ln n). There are only 1077 atoms in the universe. If every atom in the universe needed a billion new primes every microsecond from the beginning of time until now, you would only need 10¹⁰⁹ primes.
What if two people accidentally pick up the same prime number? It won’t happen. With over 10¹⁵¹ prime numbers to choose from, the odds of that happening is significantly low.
If someone creates a database of all primes, won’t he be able to use that database to break public-key algorithms? Yes, but he can’t do it. If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weight so much that it would exceed the Chandrasekhar limit and collapse into a black hole &ldots; so you couldn’t retrieve the data anyway.

But if factoring numbers is so hard, how can generating prime numbers be easy? The trick is that the yes/no question, "Is n prime?" is a much easier question to answer than the more complicated question, "What are the factors of n?"

The wrong way to find primes is to generate random numbers and then try to factor them. The right way is to generate random numbers and test if they are prime. There are several probabilistic primality tests; tests that determine whether a number is prime with a given degree of confidence. Assuming this "degree of confidence" is large enough, these sorts of tests are good enough.

Various primality-testing algorithms include:

Solovay-Strassen Test
Lehmann Test
Rabin-Miller Test
Fermat’s Test

The algorithm everyone uses was developed by Michael Rabin, based in part on Gary Miller’s ideas. Actually, this is a simplified version of the algorithm recommended in the DSS proposal.

Rabin-Miller Test

Choose a random number, p, to test. Calculate b, where b is the number of times 2 divides p-1. Then calculate m, such that p = 1 + 2^b*m.

1. Choose a random number, a, such that a is less than p.
2. Set j = 0, and set z = a^m mod p.
3. If z = 1, or if z = p - 1, then p passes the test and may be prime.
4. If j > 0 and z = 1, then p is not prime.
5. Set j = j +1. If j < b and z <> z² mod p go back to step 4. If z = p - 1, then p passes the test and may be prime.
6. If j = b and z <> p -1, then p is not prime.

The odds of a composite passing decreases faster with this test than with previous ones. Three-quarters of the possible values of a are guaranteed to be witnesses. This means that a composite number will slip through t tests no more than ¼t of the time, where t is the number of iterations. Actually, these numbers are very pessimistic. For most random numbers, something like 99.9 percent of the possible a values are witnesses.

Fermat’s Test

If p is a prime, then Fermat’s test says 2^p mod p = 2

This can be used as an additional level of testing, during the prime number generation phase.

Practical Considerations

In real-world implementations, prime generation goes quickly.

Generate a random n-bit number, p.
Set the high-order and low-order bit to 1. (The high-order bit ensures that the prime is of the required length and the low-order bit ensures that it is odd.)
Check to make sure p is not divisible by any small primes: 3, 5, 7, 11 and so on. Many implementations test p for divisibility by all primes less than 256. The most efficient is to test for divisibility by all primes less than 2000.
Perform the Rabin-Miller test for some random a. If p passes, generate another random a and go through the test again. Choose a small value of a to make the calculations go quicker. Do five tests. (One might seem like enough, but do five!). If p fails one of the tests, generate another p and try again.

Another option is not to generate a random p each time, but to incrementally search through numbers starting at a random point until you find a prime.

Step (3) is optional, but it is a good idea. Testing a random odd p to make sure it is not divisible by 3, 5, and 7 eliminates 54 percent of the odd numbers before you get to step (4). Testing against all primes less than 100 eliminates 76 percent of the odd numbers; testing against all primes less than 256 eliminates 80 percent. In general, the fraction of odd candidates that is not a multiple of any prime less than n is 1.12/ln n. The larger the n you test up to, the more precomputation is required before you get to the Rabin-Miller test.

Strong Primes

If n is the product of two primes, p and q, it may be desirable to use strong primes for p and q. These are prime numbers with certain properties that make the product n difficult to factor by specific factoring method. Among the properties suggested have been:

The greatest common divisor of p-1 and q-1 should be small.
Both p-1 and q-1 should have large prime factors, respectively p’ and q’.
Both p’-1 and q’-1 should have large prime factors.
Both p+1 and q+1 should have large prime factors.
Both (p-1)/2 and (q-1)/2 should be prime. (Note that if this condition is true, then so are the first two).

Whether strong primes are necessary is a subject of debate. These properties were designed to thwart some older factoring algorithms. However, the fastest factoring algorithms have as good a chance of factoring numbers that meet these criteria.

http://www.anujseth.com/crypto/prime.html