lundi 19 juillet 2021

What are some alternatives to Linear Congruential Generator for generation of shortcodes?

LCG can be used to generate pseudorandom numbers. With carefully selected parameters, it can have an arbitrarily high period and will output every number up to its modulus m, exactly once per cycle.

The output of the generator can then be mapped to a string, for example to generate a shortcode or unique ID which doesn't necessarily need to be secure.

What are some other algorithms which can accomplish the same task but might have differing strengths and weaknesses compared to LCG?

The LCG is working fine for what I need. PRNGs are a new topic for me, and I am asking this question more to discover what else is out there, rather than to find a replacement for what I am already using.

I've included code for my LCG implementation in JavaScript, in case it helps to answer the question.

class LinearCongruentialGenerator {
    constructor(m, x, a, c) {
        this.m = m;
        this.x = x;
        this.a = a;
        this.c = c;
    }

    get seed() {
        this.x = (this.a * this.x + this.c) % this.m;
        return this.x;
    }
}

/***
 * m can be selected mostly arbitrarily
 * a, c will later be selected so that the period of our LCG is m
 * m = 2**32 = 4294967296.
 */
const m = 4294967296;

/***
 * 0 < c < m; c and m should be relatively prime, so c is odd.
 * c = 1 for simplicity.
 * 
 * although not required by the algorithm, c < a to prevent issues with overflow.
 */
const c = 1;


/***
 * a is carefully selected to meet the following criteria:
 * (a - 1) mod 4 = 0;
 * ((a - 1) / 4) and m are relatively prime;
 * a <= 2**21.
 * 
 * 2**21 = 2097152 is selected as an upperbound for a
 * to prevent overflowing JavaScript's safe integer range, 2**53 - 1
 * 
 * this selection is based off our earlier selection of m = 2**32.
 * if m is larger than 2**32, then a should be adjusted again.
 * 
 * (if a = 4*b + 1, and a <= 2097152, then b <= 524287)
 */
const a = 4*30713 + 1

/***
 * if the generator is resuming, then x should be set to the last known seed
 * if the generator is new, then x can be selected arbitrarily, such that 0 <= x < m
 */
const x = 1;


// Setup and run the generator until we find the initial value.

let lcg = new LinearCongruentialGenerator(m, x, a, c);
const seed_0 = lcg.seed;

let i = 1;

const t_start = Date.now();
while (seed_0 != lcg.seed) {
    i++;
}
const t_end = Date.now();

// Took 4294967296 iterations and 55604 ms to complete.
console.log(`Took ${i} iterations and ${t_end - t_start} ms to complete.`);



Aucun commentaire:

Enregistrer un commentaire