Generating Random Factored Numbers, Easily

April 17, 2018

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.

Advertisements

Pages: 1 2

3 Responses to “Generating Random Factored Numbers, Easily”

  1. Paul said

    In Python.
    from random import randrange
    from ma.primee import is_prime

    def kalai(n):
    while True:
    s, r = n, 1
    while s > 1:
    s = randrange(1, s)
    if is_prime(s):
    r *= s
    if r <= n and randrange(1, n+1) <= r:
    return r

  2. Paul said

    Oops, forgot to format.

    from random import randrange
    from ma.primee import is_prime
    
    def kalai(n):
        while True:
            s, r = n, 1
            while s > 1:
                s = randrange(1, s)
                if is_prime(s):
                    r *= s
            if r <= n and randrange(1, n+1) <= r:
                    return r
    
  3. Paul said

    A later and more correct version is on ideone.

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: