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 ≤ r ≤ n.
- Generate a seqneuce n ≥ s1 ≥ s2 ≥ … ≥ si = 1 by choosing s1 ∈ {1, 2, …, n} and si+1 ∈ {1, 2, … si}, until reaching 1.
- Let r be the product of the prime si‘s.
- If r ≤ n, output r with probability r / n.
- 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.
Programming Praxis 
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
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 rA later and more correct version is on ideone.
Here’s a solution in C++11 using GMP. Prime checking is probabilistic and can return false positives with some non-zero probability (and consequently a factorization that can include composites).
/* random_factored.cpp */ // Build // $ g++ -std=c++11 \ // random_factored.cpp \ // -o random_factored \ // -lgmpxx -lgmp #include <cstdlib> #include <chrono> #include <vector> #include <gmpxx.h> using std::vector; void random_factored(const mpz_class& max, mpz_class* rand, vector<mpz_class>* factors, int reps = 50) { using namespace std::chrono; gmp_randclass rng(gmp_randinit_default); auto now = system_clock::now(); auto ms = time_point_cast<milliseconds>(now); long seed = ms.time_since_epoch().count(); rng.seed(seed); mpz_class s; while (true) { s = max; *rand = 1; factors->clear(); while (s > 1) { s = rng.get_z_range(s) + 1; if (mpz_probab_prime_p(s.get_mpz_t(), reps)) { *rand *= s; if (*rand > max) goto contin; factors->push_back(s); } } if ((rng.get_z_range(max) + 1) <= *rand) return; contin:; } } int main(int argc, char* argv[]) { if (argc != 2) { fprintf(stderr, "Usage: random_factored <MAX>\n"); return EXIT_FAILURE; } mpz_class max(argv[1], 10); mpz_class rand; vector<mpz_class> factors; random_factored(max, &rand, &factors); gmp_printf("%Zd\n\n", rand.get_mpz_t()); for (const mpz_class factor : factors) { gmp_printf("%Zd\n", factor.get_mpz_t()); } return EXIT_SUCCESS; }Example:
[…] Read More […]