A Blum Blum Shub pseudorandom RNG implementation in JavaScript

Question

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.

Answer 1

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.