Cryptology III.3 Primality Tests

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The pseudoprime test [PDF]
2. Strong pseudoprimes [PDF]
3. MILLER's primality test [PDF]
4. The extended RIEMANN hypothesis (ERH) [PDF]
5. RABIN's probabilistic primality test [PDF]
6. RSA and pseudoprimes [PDF]
7. The AKS primality test [PDF]
8. The AKS algorithm [PDF]

The complete chapter as PDF file

Overview

A crucial question when implementing RSA is how to find the necessary primes for key generation. The answer will be given in form of efficient procedures. Start with a random integer of the desired length and test it for primality. If it is not prime take the next integer and so on. Eventually a prime will occur.

For this we need procedures that efficiently decide whether an integer is prime or not—primality tests.

We'll encounter a phenomenon that is familiar also with other mathematical problems (for instance linear optimization, numerical approximation of roots of polynomials over the real or complex numbers):

• There is an algorithm that gets by with polynomial cost.
• There is a »standard algorithm« (in the examples: the simplex method, the Newton algorithm) that is more efficient for »most« instances, but needs more than polynomial cost in the »worst case«. In practice this algorithm is the preferred one.

All these primality tests have a considerable overhead. Therefore for a practical implementation it makes sense to first check divisibility by »small« primes, say primes < 10⁶, depending on the available storage (precompute a list L of small primes).

If we need a random prime of a certain size we randomly choose an integer r of this size. If r is even we increment it by 1. Then we sieve an interval [r, r+s] for multiples of the primes in L by ERASTOTHENES' method. We test the remaining integers for primality until we find one that passes the test. In most cases this will be the first one already.