3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The code and its updates are available on Gist: gist.github.com/schas002/757c0b948b469cd591c24f27eb16edf0 \$\endgroup\$ – zyabin101 Jul 3 '16 at 9:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ry- Jul 3 '16 at 9:39
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.