## 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.

Pages: 1 2

### 5 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.

4. Daniel said

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, 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:

```\$ ./random_factored 1000
690

23
5
3
2
```
5. […] Read More […]