Generating Random Factored Numbers, Easily

April 17, 2018

Here’s our version of the function, which uses the native Chez Scheme random-number function:

; composite number between lo and hi, with its prime factorization
(define (random-composite lo hi) ; j cryptology (2003) 16: 287-289
  (let loop ((n hi) (ss (list)))
    (if (< 1 n) (let ((t (+ (random n) 1))) (loop t (cons t ss)))
      (let* ((rs (filter prime? ss)) (r (apply * rs)))
        (if (and (< 1 (length rs)) (< lo r hi) (< (random 1.0) (/ r hi)))
            (values r rs)
            (random-composite lo hi))))))

And here are some examples:

> (random-composite #e1e49 #e1e50)
39031688906845405947838510008765610782589401947814
(2 3 3 3 23819 472116863
   64276252279614685494838344056247653)
> (random-composite #e1e199 #e1e200)
54043199014242862074068285893135249110810396044949893213716035706818704365084807
10747697771435656989138804427933641862633849990995410369411218898581482115751406
0271041039310245242619801236797864316382
(2 32551107389
   18297496992808352052439
   6412310674737823761171618278424510901936500685202576340621797
   70752052794845144427307913529578325615157382037282566979843347735524206867191
74656452808739750971865168793)

You can run the program at https://ideone.com/106ySG, where you will also see our Baillie-Wagstaff primality checker. Beware that it gets slower as hi gets larger.

Advertisements

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

    $ ./random_factored 1000
    690
    
    23
    5
    3
    2
    

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 )

Connecting to %s

%d bloggers like this: