Admin: Created page with "'''Bach's algorithm''' is a probabilistic polynomial time algorithm for generating random numbers along with their factorization,..."

2019-04-11T04:05:19Z

Created page with "'''Bach's algorithm''' is a probabilistic polynomial time algorithm for generating random numbers along with their factorization,..."

New page

'''Bach's algorithm''' is a probabilistic [[polynomial time]] [[algorithm]] for generating [[pseudorandom number generator|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(log<sup>2</sup> n) primality tests), is known and is due to [[Adam Kalai]]

== Overview ==

Bach's algorithm produces a number ''x'' uniformly at random between a given limit ''N'' and ''N''/2, specifically <math>\frac{N}{2} < x \le N</math>, along with its factorization. It does this by picking a [[prime number]] ''p'' and an exponent ''a'' such that <math>p^a \le N</math>, 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 <math>M = \frac{N}{p^a}</math>, along with the factorization of ''y''. It then sets <math>x = p^{a}y</math>, and appends <math>p^a</math> 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.

* [[Eric Bach|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 [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s02/www/dartboard.pdf here].

==Source==

[http://wikipedia.org/ http://wikipedia.org/]
==See Also on BitcoinWiki==
* [[Bitcoin.Me]]
* [[Bitcoin Blogger]]
* [[Abitgreedy]]
* [[Sources and Services]]
* [[Bitbook.ie]]

Bach's algorithm - Revision history

Admin: Created page with "'''Bach's algorithm''' is a probabilistic polynomial time algorithm for generating random numbers along with their factorization,..."