Photo by Carson Arias on Unsplash

Go be rAnd0m with Blum Blum Shub

It sounds like backing vocals from a famous Beatles track … “Blum Blum Shub” … but it’s not … it’s the best provable pseudo-random number generator around … Blum Blum Shub [here]:

The Blum Blum Shub (BBS) method is a pseudorandom number generator and was created by Lenore Blum, Manuel Blum and Michael Shub in 1986. It uses the form of:

and where x_0 is a random seed. The value of M is equal to pq, and where p and q are prime numbers. These values of p and q are both congruent to 3 mod 4 (p=q=3 (mod4) ). What does that mean? Well when I take the values of p or q and divide them by 4, I will get a remainder of 3.

So, p=7 is possible (as 7 divided by 4 is 1, remainder 3), and p=11 is also possible (as 11 divided by 4 is 2, remainder 3). A value of 13 is not possible is at will be 3, remainder 1. Let’s try a simple example in Python [here]:

>>> p=7
>>> q=11
>>> M=p*q
>>> x0=5
>>> x1=(x0**2)%M
>>> x2=(x1**2)%M
>>> x3=(x2**2)%M
>>> x4=(x3**2)%M
>>> print (x1,x2,x3,x4)
25 9 4 16

In this case we are using p=7 and q=11, and then a seed of x_0=5, and the random sequence is 25, 9, 4 and 16. We normally just take the least…