Programming Praxis

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 ≤ r ≤ n.

1. Generate a seqneuce n ≥ s₁ ≥ s₂ ≥ … ≥ s_i = 1 by choosing s₁ ∈ {1, 2, …, n} and s_i+1 ∈ {1, 2, … s_i}, until reaching 1.
2. Let r be the product of the prime s_i‘s.
3. If r ≤ n, 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