Bach's algorithm

566pages on
this wiki
Add New Page
Talk0 Share

Bach's algorithm[1] is a probabilistic polynomial time algorithm for generating random numbers along with their factorization, 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, O(log2 n) primality tests), is known and is due to Adam Kalai[2]

Overview Edit

Bach's algorithm produces a number x uniformly at random between a given limit N and N/2, specifically \frac{N}{2} < x \le N, along with its factorization. It does this by picking a prime number p and an exponent a such that p^a \le N, 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 M = \frac{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 which logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.

References Edit

  1. Bach, Eric. How to Generate Factored Random Numbers, SIAM Journal of Computing, 17 (1988), pp 179-193.
  2. Generating Random Factored Numbers, Easily: Adam Kalai, Journal of Cryptology, Vol 16, Number 4, 2003
  • 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.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.