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.^[1][5]

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