Overview
All data
5 statements · 0% with external sources · numbers in brackets are citations
- Discovered
- 1988
- Average time complexity
O(\log n)
On other databases
1 identifiers linking Bach's algorithm across the web's reference databases
5 statements · 0% with external sources · numbers in brackets are citations
O(\log n) 1 identifiers linking Bach's algorithm across the web's reference databases
From Wikipedia, the free encyclopedia · Read full article · Text CC BY-SA 4.0
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.