Generating RandomFactoredNumbers,Easily
Adam Kalai*
Our goal is to generate a random “pre-factored”
number, that is a uniformly random number between 1
and N, along with its prime factorization. Of course,
one could simply pick a random number and then p < N and generating the factored number r = [I pap try to factor it, but there is no known polynomial-
time factoring algorithm [3]. In his dissertation, Bach
presents an efficient algorithm for generating such pre-
factored numbers [1, 2]. Here, we present a significantly
simpler algorithm and analysis for the same problem.
Our algorithm is, however, a log(N) factor less efficient.
Algorithm:
Input: Integer N > 0.
Output: A uniformly random number 1 < m < N. 1. Pick random seq. N > sl > s2 _>… > st = 1 by
choosing sl E {1,2,…,N} and si+l e {1,2,…,si}. 2. Let r be the product of the prime si’s.
3. If r _