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 &gt; 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.
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.