Fast verification,testing, and generation of large primes

We present a prime certification method which permits shorter certificates of primality than the method analyzed by Pratt. We analyze the expected time required by a stochastic method for showing that n is prime, given a factorization of n ? 1. We use this method, together with Rabin's stochastic method for verifying compositeness, to obtain an algorithm for generating arbitrarily large primes and short certificates of their primality. We give plausibility arguments that this method can generate primes larger than n in expected time polynomial in log n. We analyze several such prime generation algorithms.