Skip to content

Michael Forbes: Generating Random Pre-factored Integers

by on February 19, 2012

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.

Advertisements
One Comment
  1. (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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: