Bach's algorithm is a probabilistic
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for
generating random numbers along with their
factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
s, named after its discoverer,
Eric Bach. It is of interest because no algorithm is known that efficiently factors numbers, so the straightforward method, namely generating a random number and then factoring it, is impractical.
The algorithm performs, in expectation, O(log n)
primality tests
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wh ...
.
A simpler, but less efficient algorithm (performing, in expectation,
primality tests), is due to
Adam Kalai.
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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
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
In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of ...
is then used to get a uniform distribution.
References
Further reading
*
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 onlin
here
Cryptographic algorithms
Random number generation
{{algorithm-stub