Bach's algorithm is a probabilistic polynomial time algorithm for generating random numbers along with their factorization, named after its discoverer, Eric Bach. It is of interest because no algorithm is known that efficiently factors numbers, so the straightforward method, namely generating a random number and then factoring it, is impractical.
The algorithm performs, in expectation, O(log n) primality tests.
A simpler, but less efficient algorithm (performing, in expectation, O(log2 n) primality tests), is known and is due to Adam Kalai
Overview
Bach's algorithm produces a number x uniformly at random between a given limit N and N/2, specifically