# Michael Forbes: Generating Random Pre-factored Integers

One neat algorithm: Generating a uniform prime in [n], along with the factorization of p-1, all in expected poly(n) time. (Assumes some primality testing algo. Given an RP algorithm, some error in the distribution occurs. With AKS, get the exact distribution).

It was first done by Eric Bach (say 1970’s), but then was simplified (but worse running time) by Adam Kalai post 2000. The main idea is to first generate a random number m in [n], and then repeat until m is prime. To generate such an m, we can follow the heuristic that we take all primes in [n], and for such a prime p, we return p^e with probability 1/p^e, with suitable normalization so this is a probability distribution. We then output the product of all such p^e. Thus, a number m will be generated with probability 1/m. If we keep that number with probability m/n (and otherwise repeat the algorithm), then we have generated m with probability 1/n. One can show that there is a probability 1/lg n of success (using Merten’s theorem).

However, the issue in the above is that we cannot loop through all primes in [n], as there are too many. Even if we did, not that many primes would even generate p^e with e>0, so most of that time would be wasted. Thus, to make the above efficient, we will develop an alternate way to sample from the desired distribution. The following process works: start with n, and select uniformly from [n]. Call the result t. Then select uniformly from [t], and repeat this process with the new value. One can show that the resulting distribution has that a number m is output e times with probability 1/m^e (pre-normalization). Thus, performing this process, and then selecting the primes, will yield the needed distribution to select a uniform number from [n].

For details, the book by Shoup (see http://shoup.net/ntb/ for an online coup) has a nice writeup.

(Adam) Kalai’s paper on generating prefactored integers is one of my favorites too. In particular I love the “random non-decreasing sequence” concept you mention above. Stripping number theory (primality etc.) away, the random process is described by the random variable X(n), where

where X(1) = empty sequence and X(n) = alpha followed by X(alpha) where alpha is chosen uniformly from {1…n}.

One of the most intriguing phenomena exposed in this paper is the following: Let B_{i,n} be

the event that i appears in the sequence X(n). Question: for 1 <= i < j <= n, are the events

B(i,n) and B(j,n) independent? Very counterintuitively (at least to me) the paper notices

that they are, and then builds on this!

– Madhu