Bach’s algorithm
Bach’s algorithm is a probabilistic algorithm for generating numbers along with their , named after its discoverer, . 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) .
A simpler, but less efficient algorithm (performing, in expectation, O(log<sup>2</sup> n) primality tests), is known and is due to
Overview
Bach’s algorithm produces a number x uniformly at random between a given limit N and N/2, specifically <math>frac{N}{2} < x le N</math>, along with its factorization. It does this by picking a p and an exponent a such that <math>p^a le N</math>, according to a certain distribution. Bach’s algorithm is then recursively applied to generate a number y uniformly at random between M and M/2, where <math>M = frac{N}{p^a}</math>, along with the factorization of y. It then sets <math>x = p^{a}y</math>, and appends <math>p^a</math> to the factorization of y to produce the factorization of x. This gives x which logarithmic distribution over the desired range; is then used to get a uniform distribution.
- . 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.