Bach's algorithm

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, 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]

  1. ^ Bach, Eric (1988). "How to generate factored random numbers". SIAM Journal on Computing. 17 (2): 179–193. doi:10.1137/0217012. MR 0935336.
  2. ^ Kalai, Adam (2003). "Generating random factored numbers, easily". Journal of Cryptology. 16 (4): 287–289. doi:10.1007/s00145-003-0051-5. MR 2002046. S2CID 17271671.
  3. ^ Shoup, Victor (2008). A Computational Introduction to Number Theory and Algebra (Version 2 ed.). Cambridge, UK: Cambridge University Press. p. 305.
  4. ^ Delfs, Hans; Knebl, Helmut (2015). Introduction to Cryptography: Principles and Applications (3rd ed.). Berlin: Springer Verlag. p. 226.