A Blum Blum Shub pseudorandom RNG implementation in JavaScript

I made a Blum Blum Shub pseudorandom number generator implementation in JavaScript.

Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's oblivious transfer mapping.

Blum Blum Shub takes the form

$x_{n+1}=x_{n}^{2}{\bmod {M}}$

where M = pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from $x_{n+1}$; the output is commonly either the bit parity of $x_{n+1}$ or one or more of the least significant bits of $x_{n+1}$.

The seed $x_0$ should be an integer that is co-prime to M (i.e. p and q are not factors of $x_0$) and not 1 or 0.

The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(φ(p − 1), φ(q − 1)) should be small (this makes the cycle length large).

-- from Wikipedia

var p = 5651;
var q = 5623;
var M = p * q;

var x = undefined;

/** Get the gcd of two numbers, A and B. */
function gcd(a, b) {
while(a != b) {
if(a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}

/** Seed the random number generator. */
function seed(s) {
if(s == 0) {
throw new Error("The seed x[0] cannot be 0");
} else if(s == 1) {
throw new Error("The seed x[0] cannot be 1");
} else if(gcd(s, M) != 1) {
throw new Error("The seed x[0] must be co-prime to " + M.toString());
} else {
x = s;
return s;
}
}

/** Get next item from the random number generator. */
function next() {
var cachedx = x;
cachedx = cachedx * x;
cachedx = cachedx % M;
x = cachedx;
return x;
}


The code might be able to be refactored to an object and a factory generating such objects, for independent states and functions of the generator. I'm interested if there are any more problems with this code.

• The code and its updates are available on Gist: gist.github.com/schas002/757c0b948b469cd591c24f27eb16edf0 – zyabin101 Jul 3 '16 at 9:19
• Primes large enough to be secure won't fit into JavaScript integers, but if this is just to try things out on a small scale I suppose that doesn't matter. – Ry- Jul 3 '16 at 9:39

You haven't declared cachedx, so it's implicitly global. Turn on strict mode (put 'use strict'; at the top of your script) to prevent this in the future. I'm not sure why cachedx would be necessary anyway, though:

/** Get next item from the random number generator. */
function next() {
x = x * x % M;
return x;
}


Also, there's no point in initializing things to undefined. That's the default. The chance that something might be uninitialized when you attempt to use it is a bad sign, though, and you're probably right that it would be better to be able to create instances of the generator:

function Random(p, q, seed) {
var m = p * q;

if (seed == 0) {
throw new Error("The seed x[0] cannot be 0");
} else if (seed == 1) {
throw new Error("The seed x[0] cannot be 1");
} else if (gcd(seed, m) != 1) {
throw new Error("The seed x[0] must be co-prime to " + m);
}

this.m = m;
this.state = seed;
}

Random.prototype.next = function () {
var x = this.state;
var next = x * x % this.m;

this.state = next;
return next;
};


noting that you don't need to call toString to concatenate a string and a number.