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.