# 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.