A very efficient recursive algorithm for generating nearly random prov
able primes is presented. The expected time for generating a prime is
only slightly greater than the expected time required for generating a
pseudoprime of the same size that passes the Miller-Rabin test for on
ly one base. Therefore our algorithm is even faster than algorithms pr
esently used for generating only pseudoprimes because several Miller-R
abin tests with independent bases must be applied for achieving a suff
icient confidence level. Heuristic arguments suggest that the generate
d primes are close to uniformly distributed over the set of primes in
the specified interval. Security constraints on the prime parameters o
f certain cryptographic systems are discussed, and in particular a det
ailed 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 satisf
y these security constraints. Further results described in this paper
include an analysis of the optimal upper bound for trial division in t
he 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-modu
lus, given a security bound on the size of the two primes.