Adam Kalai
akalai@cs.cmu.edu
Consider the problem of generating a random ``pre-factored'' number, that is a
uniformly random number between 1 and N, along with its prime
factorization. In his dissertation, Erich Bach presents an efficient algorithm
for this problem [1, 2]. Here, we present a significantly simpler
algorithm and analysis for the same problem. Our algorithm is, however, a
factor less efficient.
The key to understanding this algorithm is that each prime is
included in the sequence independently with probability
. Intuitively,
this is because p occurs iff it is chosen before
, which
happens with probability
. As a result, the probability of generating a
factored number
is proportional to
. Step 3 then makes each number
equally likely with rejection sampling.
We could have equivalently, but more slowly, generated the sequence in Step 1
by first choosing the number of occurrences of N, and then generating such a
sequence for N-1. This follows from the fact that, regardless of the number
of occurrences of N, the first number in the sequence less than N is
equally likely to be . Clearly N occurs at least once with
probability
and occurs exactly
times with probability
. It follows, by induction on N, that the probability of
having
occurrences of j is
, and that
occurrences of different j are independent.
The chance of having occurrences of each prime
and
generating the factored number
in Step 2 is, by
independence,
Thus the probability of generating an and outputting it in
Step 3 is
, which means
that all
are equally likely. So, with probability
we
output a uniformly random factored number, and otherwise we
restart. Consequently, the expected number of restarts is
, by Merten's theorem [3]. On a run, we expect to
execute
primality tests, giving an expected
primality tests before success. Bach's algorithm uses only
an expected
tests. For either algorithm, primality tests can be
implemented efficiently by a randomized algorithm.
Acknowledgements. I would like to thank Manuel Blum, Michael Rabin, and Doug Rohde for helpful comments.