Sometimes it is convenient to have large random composite numbers with known factorization, particularly for testing prime number programs. Eric Bach gives a fast but complicated method. Adam Kalai gives a simpler method that’s not so fast:

Input: Integer n > 0.

Output: A uniformly random number 1 ≤ rn.

  1. Generate a seqneuce ns1s2 ≥ … ≥ si = 1 by choosing s1 ∈ {1, 2, …, n} and si+1 ∈ {1, 2, … si}, until reaching 1.
  2. Let r be the product of the prime si‘s.
  3. If rn, output r with probability r / n.
  4. Otherwise, RESTART.

Your task is to implement Kalai’s method of generating random composite numbers with their factorization. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2