[SOLVED] CS AI algorithm Generating RandomFactoredNumbers,Easily

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, Bachpresents an efficient algorithm for generating such pre-factored numbers [1, 2]. Here, we present a significantlysimpler 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 sis.
3. If r _