Bach's algorithm is a probabilistic polynomial time algorithm for generating random numbers along with their factorizations, 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, primality tests), is due to Adam Kalai.