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]

Overview

edit

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]

References

edit
  1. ^ a b 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.
  5. ^ Granville, Andrew; Granville, Jennifer (2019). "Constructing integers with the probabilistic model". Prime Suspects: The Anatomy of Integers and Permutations. Princeton University Press. pp. 207–208. ISBN 9780691188737.

Further reading

edit
  • 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.