Bach's algorithm is a probabilistic polynomial time algorithm for generating random numbers along with their factorization. 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.

The algorithm performs, in expectation, primality tests. A simpler but less-efficient algorithm (performing, in expectation, primality tests), is due to Adam Kalai.

Bach's algorithm may be used as part of certain methods for key generation in cryptography.

Overview

), along with its factorization. It does this by picking a prime number with logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.

References

Further reading

• Bach, Eric. Analytic methods in the Analysis and Design of Number-Theoretic Algorithms, MIT Press, 1984. Chapter 2, "Generation of Random Factorizations", part of which is available online here.