# 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 [itex]frac{N}{2} < x le N[/itex], along with its factorization. It does this by picking a p and an exponent a such that [itex]p^a le N[/itex], 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 [itex]M = frac{N}{p^a}[/itex], along with the factorization of y. It then sets [itex]x = p^{a}y[/itex], and appends [itex]p^a[/itex] 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.

## Source

http://wikipedia.org/