Encyclopedia

Bach's algorithm

For generation of random factorized numbers

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated May 28, 2026

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, O(log n) primality tests. A simpler but less-efficient algorithm (performing, in expectation, O(log² n) primality tests), is due to Adam Kalai.

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

01Overview

Bach's algorithm produces a number $x$ uniformly at random in the range $N/2<x\leq N$ (for a given input $N$ ), along with its factorization. It does this by picking a prime number $p$ and an exponent $a$ such that $p^{a}\leq N$ , according to a certain distribution. The algorithm then recursively generates a number $y$ in the range $M/2<y\leq M$ , where $M=N/p^{a}$ , along with the factorization of $y$ . It then sets $x=p^{a}y$ , and appends $p^{a}$ to the factorization of $y$ to produce the factorization of $x$ . This gives $x$ with logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.

Watch videos about Bach's algorithmExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Bach's algorithm”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.