Bach's algorithm is a probabilistic polynomial time algorithm for generating random numbers along with their factorizations.
It was published by Eric Bach in 1988.
No algorithm is known that efficiently factors random numbers, so the straightforward method, namely generating a random number and then factoring it, is impractical.
[1] The algorithm performs, in expectation, O(log n) primality tests.
A simpler but less-efficient algorithm (performing, in expectation, O(log(n)2) primality tests), is due to Adam Kalai.
[2][3] Bach's algorithm may be used as part of certain methods for key generation in cryptography.
[4] Bach's algorithm produces a number
uniformly at random in the range
It does this by picking a prime number
The algorithm then recursively generates a number
to produce the factorization of
with logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.
[1][5] This algorithms or data structures-related article is a stub.