Bach's algorithm

{{short description|Algorithm for generating random numbers with their factorization}}

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.{{cite journal

| last = Bach | first = Eric | authorlink = Eric Bach

| doi = 10.1137/0217012

| issue = 2

| journal = SIAM Journal on Computing

| mr = 935336

| pages = 179–193

| title = How to generate factored random numbers

| volume = 17

| year = 1988}}

The algorithm performs, in expectation, {{Math|O(log n)}} primality tests. A simpler but less-efficient algorithm (performing, in expectation, {{Math|O(log(n)²)}} primality tests), is due to Adam Kalai.{{cite journal

| last = Kalai | first = Adam

| doi = 10.1007/s00145-003-0051-5

| issue = 4

| journal = Journal of Cryptology

| mr = 2002046

| pages = 287–289

| title = Generating random factored numbers, easily

| volume = 16

| year = 2003| s2cid = 17271671

| doi-access = free

}}{{cite book |last1=Shoup |first1=Victor |title=A Computational Introduction to Number Theory and Algebra |date=2008 |publisher=Cambridge University Press |location=Cambridge, UK |page=305 |edition=Version 2}}

Bach's algorithm may be used as part of certain methods for key generation in cryptography.{{cite book |last1=Delfs |first1=Hans |last2=Knebl |first2=Helmut |title=Introduction to Cryptography: Principles and Applications |date=2015 |publisher=Springer Verlag |location=Berlin |page=226 |edition=3rd}}

Overview

Bach's algorithm produces a number $x$ uniformly at random in the range $N/2 < x \le N$ (for a given input $N$ ), along with its factorization. It does this by picking a prime number $p$ and an exponent $a$ such that $p^a \le N$ , according to a certain distribution. The algorithm then recursively generates a number $y$ in the range $M/2 < y \le M$ , where $M = N/p^a$ , along with the factorization of $y$ . It then sets $x = p^{a}y$ , and appends $p^a$ to the factorization of $y$ to produce the factorization of $x$ . This gives $x$ with logarithmic distribution over the desired range; rejection sampling is then used to get a uniform distribution.{{cite book|title=Prime Suspects: The Anatomy of Integers and Permutations|first1=Andrew|last1=Granville|first2=Jennifer|last2=Granville|publisher=Princeton University Press|year=2019|isbn=9780691188737|contribution=Constructing integers with the probabilistic model|pages=207–208|contribution-url=https://books.google.com/books?id=uPaKDwAAQBAJ&pg=PA207}}

Bach's algorithm

Overview

References

Further reading