6 Staged algorithms and random primes
Suppose a randomized computation is divided into stages, each stage consumes at most \(n\) random bits, and the information retained between stages uses at most \(w\) bits. Then replacing the stage randomness by the blocks of a pseudorandom generator for \(\operatorname {Space}(w)\) and block size \(n\) changes the final output distribution by at most the generator parameter, for every event that can be tested from the final state.
Model the retained inter-stage information as the state of a finite state machine, with one transition per stage labelled by the random block values that lead to each next retained state. The event of interest is represented by the accepting states after the final stage. Definition 2 is exactly the statement that the acceptance probability changes by at most the generator parameter.
Given \(N=2^n\), repeat the following loop until success: choose a random integer \(x\) in \(\{ 1,\ldots ,N\} \), test whether \(x\) is prime, and stop if the test says prime. Output the final \(x\).
There is a randomized primality-test stage using \(O(n)\) random bits and \(O(n)\) retained space such that every prime is accepted and every composite \(n\)-bit integer is rejected with probability at least \(1/2\) by one stage. Repeating \(O(n)\) independent stages makes the probability of accepting a composite exponentially small in \(n\).
The Rabin–Miller test chooses a random witness modulo the candidate integer and performs modular exponentiations using \(O(n)\)-bit arithmetic. For a composite input, at least half of the possible witnesses reveal compositeness; for a prime input, no witness falsely rejects. The current candidate, the witness, and the modular-exponentiation workspace use \(O(n)\) bits. Repeating the basic test \(O(n)\) times multiplies the probability of missing compositeness by at most \(2^{-O(n)}\).
For \(N=2^n\), the expected number of candidate choices made by Algorithm 38 before a prime is found is \(O(n)\).
The prime number theorem gives density \(\Theta (1/\log N)=\Theta (1/n)\) for primes in \(\{ 1,\ldots ,N\} \). Each independently chosen candidate is prime with probability \(\Theta (1/n)\), so the waiting time for the first prime is a geometric random variable with expectation \(O(n)\).
A nearly uniform random prime in the range \(\{ 1,\ldots ,2^n\} \) can be generated using only \(O(n\log n)\) truly random bits.
Break Algorithm 38 into stages: one stage chooses the candidate \(x\), and each basic Rabin–Miller witness check is one additional stage. By Lemma 39, every stage consumes \(O(n)\) random bits and retains only \(O(n)\) bits between stages, mainly the candidate \(x\) and loop counters. By Lemma 40, \(O(n)\) candidate stages suffice in expectation, and the primality checks can be repeated enough times that false acceptance of a composite has exponentially small probability. Apply Theorem 26, or equivalently the staged form in Proposition 37, with space and block size \(O(n)\) and polynomially many stages. The resulting seed length is \(O(n\log n)\), and the pseudorandom execution changes the output distribution by only the chosen exponentially small parameter.