It's Random

It's Random 

And I'm Lovin' It

I love random numbers. I just love them! It's one of those few things where everything is right and nothing is. Being from the country from where ludo originated and the country where the population  pray for hours for a favourable coin toss (yea, we are obsessed with cricket!!!), I feel my love for random numbers is not misplaced. I also love random numbers because of the pristine adrenaline rush, hacking them provides. You just feel happy with every output (Segmentation Fault is not an output). The first computer science course project in my undergraduate course was a game of poker in C. But in the recent past, I have moved past to writing random number generators instead of using one.

Being a computer science undergraduate, I might or might not understand the theory of the generation of random numbers (I have spent quite sometime in understanding Marsaglia's KISS, Mersenne Twister, Blum Blum Shub etc.), but it cannot stop me from hacking them. 

One of my favourite implemented PRNG comes with a story. It was course of Information Security and we had to propose a course project. Now, I will confirm your doubts, whatever story you have heard of Engineering students and deadlines...... they are all true, we are just never before time. So, on the last day of proposal, I, based on my professors dislike of every single PRNG present in public domain, gave a new PRNG as a proposal. Now, the description of the PRNG I implemented can be found here. It contains entropy generation modules and finally a Blum Blum Shub implementation. 

Recently, as a part my parallel programming assignment, we were asked to make a thread safe PRNG. I again went with my trusted Blum Blum Shub algorithm. Now, since I am trying to make this blog a technical one (What? You don't trust me? I am hurt), I will explain how I did it.

The basic formula of Blum Blum Shub algorithm is:

x[i] = (x[i-1]*x[i-1]) mod M

where M is a product of two large randomly generated prime numbers. 

"Large Randomly Generated Prime", every word of this phrase decides the effectiveness of the PRNG from now on. Generating these has been one of the most difficult problem I faced in my student life and I probably solved it. The trick I use is to do this is a rather simple one. I generate two large numbers and perform multiple iterations of Fermat's primality test on every number greater than this till I get one. This is a slow process and can generate only what is called "Probable Primes" (I said, I only probably solved it). Also, you can speed it up a bit by checking for only the numbers in the form of 6n-1 and 6n+1. Once we get this, we can follow the generation formula.

As for the thread safe part, just make the seed private to thread and calculate the seed from the thread state (source code can be found here and here). 

I am not very sure if these are the best way to do it and am open to suggestions.