Top Qs
Timeline
Chat
Perspective

Bach's algorithm

Algorithm for generating random numbers with their factorization From Wikipedia, the free encyclopedia

Remove ads

Bach's algorithm is a probabilistic polynomial time algorithm for generating random numbers along with their factorizations. 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.[1]

The algorithm performs, in expectation, O(log n) primality tests. A simpler but less-efficient algorithm (performing, in expectation, O(log(n)2) primality tests), is due to Adam Kalai.[2][3]

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

Remove ads

Overview

Bach's algorithm produces a number uniformly at random in the range (for a given input ), along with its factorization. It does this by picking a prime number and an exponent such that , according to a certain distribution. The algorithm then recursively generates a number in the range , where , along with the factorization of . It then sets , and appends to the factorization of to produce the factorization of . This gives with logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.[1][5]

Remove ads

References

Further reading

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads