We're required to implement Blum Blum Shub Algorithm in a pseudo random number generator. I tried searching for implementations in c# to get an idea but was unsuccessful. Some methods we're required to implement are not clear enough (or maybe I'm not getting exactly what they're asking).

Anyone could provide some help with either the code or maybe an example in a similar fashion? I have a harder time grasping concepts from text.Any help would be greatly accepted!

First, I tried following the logic of the question. With little progress, I began searching on-line for better explanations and possibly finding implementations to better understanding. Finally, I attempted to fill in some of the requested methods with what I thought made sense.

static long seed = 6367859;
static long p = 3263849;
static long q = 1302498943;
static long m = p*q;

// Generates a random bit i.e. 0 or 1 using the Blum Blum Shub Algorithm and the Least Significant Bit
private byte generateRandomBit(){ }

// Method to generate a single positive 32 bit random number using the Blum Blum Shub Algorithm.
// The generateRandomBit() method is used to generate the random bits that make up the random number
// Not complete!!
public int GenerateNextRandomNumber()
{
    int nextRandomNumber = (int)((p * seed + q) % m);

    seed = nextRandomNumber;

    return nextRandomNumber;
}

// Generates a random number between min and max.
// The GenerateNextRandomNumber() method must be used to generate the initial random number which must then be manipulated (if necessary) to be between min and max
public int GenerateNextRandomNumber(int min, int max){ }

// Uses the GenerateNextRandomNumber Method to generate a sequence of Random Numbers between the minimum and the maximum value using the Blum Blum Shub Algorithm
public int[] GenerateRadmonSequence(int n, int min, int max)
{
    int[] sequence = new int[n];

    for (int i = 0; i < n; i++)
    {
        int randNum = Math.Abs(GenerateNextRandomNumber());

        randNum = min + randNum % (max + 1 +- min);
        sequence[i] = randNum;
    }

    return sequence;
}

The result should be to generate a sequence of numbers from min to max.

2 Answers

0
Severin Pappadeux On

No, you cannot use longs for this type of RNG, it pretty much requires arbitrary precision math. And what you implemented is actually looks like Linear Congruential Generator, not Blum Blum Shub algorithm.

Here is the code to get you going, .NET Core 2.2, x64 Win10. Using BigInteger, proper algorithm I believe, and parity to get next random bit. You could use least significant bit for random bit as well.

using System;
using System.Numerics;

namespace BlumBlumSnub
{
    class Program
    {
        public static readonly BigInteger p = 3263849;
        public static readonly BigInteger q = 1302498943;
        public static readonly BigInteger m = p*q;

        public static BigInteger next(BigInteger prev) {
            return (prev*prev) % m;
        }

        public static int parity(BigInteger n) {
            BigInteger q = n;
            BigInteger count = 0;
            while (q != BigInteger.Zero) {
                count += q & BigInteger.One;
                q >>= 1;
            }
            return ((count & BigInteger.One) != BigInteger.Zero) ? 1 : 0; // even parity
        }

        public static int LSB(BigInteger n) {
            return ((n & BigInteger.One) != BigInteger.Zero) ? 1 : 0;
        }

        static void Main(string[] args)
        {
            BigInteger seed = 6367859;

            BigInteger xprev = seed;
            for(int k = 0; k != 100; ++k) {
                BigInteger xnext = next(xprev);
                int bit = parity(xnext); // extract random bit from generated BBS number using parity,
                // or just int bit = LSB(xnext);
                Console.WriteLine($"Bit = {bit}");
                xprev = xnext;
            }
        }
    }
}
0
Community On

What about this implementation:

public class BlumBlumShub
{
    private readonly ulong m;
    private ulong x;

    public BlumBlumShub(int m, int seed)
    {
        this.m = (ulong) m;
        x = (ulong)seed;
    }

    public int Next()
    {
        x = (x * x) % m;
        return (int)x;
    }
}

reference


Edit: If you really need very large number you can adapt it easily:

public class BlumBlumShub
{
    private readonly BigInteger m;
    private BigInteger x;

    public BlumBlumShub(BigInteger m, BigInteger seed)
    {
        this.m = m;
        x = seed;
    }

    public BigInteger Next()
    {
        x = (x * x) % m;
        return x;
    }
}