# Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters

## Ueli Maurer

```
```A very efficient recursive algorithm for generating nearly random
provable primes is presented. The expected time for generating a prime
is only slightly greater than the expected time required for generating
a pseudo-prime of the same size that passes the Miller-Rabin test for
only one base. Therefore our algorithm is even faster than
presently-used algorithms for generating only pseudo-primes because
several Miller-Rabin tests with independent bases must be applied for
achieving a sufficient confidence level. Heuristic arguments suggest
that the generated primes are close to uniformly distributed over the
set of primes in the specified interval.

Security constraints on the prime parameters of certain cryptographic
systems are discussed, and in particular a detailed analysis of the
iterated encryption attack on the RSA public-key cryptosystem is
presented. The prime generation algorithm can easily be modified to
generate nearly random primes or RSA-moduli that satisfy these security
constraints. Further results described in this paper include an
analysis of the optimal upper bound for trial division in the
Miller-Rabin test as well as an analysis of the distribution of the
number of bits of the smaller prime factor of a random $k$-bit
RSA-modulus, given a security bound on the size of the two primes.

Keywords: Public-key cryptography, Prime numbers, Primality proof,
Miller-Rabin test, RSA cryptosystem, Number theory.