Bach's algorithm

This article relies too much on references to primary sources. Please improve this by adding secondary or tertiary sources. (August 2021) (Learn how and when to remove this template message)

Bach's algorithm^[1] is a probabilistic polynomial time algorithm for generating random numbers along with their factorizations, named after its discoverer, Eric Bach. 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) primality tests.

A simpler, but less efficient algorithm (performing, in expectation, ${\displaystyle O(\log ^{2}n)}$ primality tests), is due to Adam Kalai.^[2]

Overview[]

This section does not cite any sources. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. (June 2020) (Learn how and when to remove this template message)

Bach's algorithm produces a number ${\displaystyle x}$ uniformly at random in the range ${\displaystyle N/2<x\leq N}$ (for a given input ${\displaystyle N}$), along with its factorization. It does this by picking a prime number ${\displaystyle p}$ and an exponent ${\displaystyle a}$ such that ${\displaystyle p^{a}\leq N}$, according to a certain distribution. The algorithm then recursively generates a number ${\displaystyle y}$ in the range ${\displaystyle M/2<y\leq M}$, where ${\displaystyle M=N/p^{a}}$, along with the factorization of ${\displaystyle y}$. It then sets ${\displaystyle x=p^{a}y}$, and appends ${\displaystyle p^{a}}$ to the factorization of ${\displaystyle y}$ to produce the factorization of ${\displaystyle x}$. This gives ${\displaystyle x}$ 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.

This algorithms or data structures-related article is a stub. You can help Wikipedia by .

• v
• t