Bach's algorithm
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 primality tests.
A simpler, but less efficient algorithm, is due to Adam Kalai.Overview
Bach's algorithm produces a number uniformly at random in the range , along with its factorization. It does this by picking a prime number and an exponent such that, according to a certain distribution. The algorithm then recursively generates a number in the range, where, along with the factorization of. It then sets, and appends to the factorization of to produce the factorization of. This gives with logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.
