Random Number Generation

Introduction

This article will examine random number generation. While not a popular topic, random number generation has many practical uses, particularly in cryptography. The random number generator provided by the .NET Framework is implemented via the System.Random class. By default, the parameterless constructor of the Random() class uses the computer's internal system clock to generate its own seed value whereas the parameterized constructor can accept specific seed values from within the allowed range of Int32 integers. According to Joe Duffy in his book "Professional .NET Framework 2.0", these numbers generated are not truly random because the class uses a deterministic algorithm to produce them. This means that the algorithm goes through the same step-by-step instructions to generate the next number in the sequence. It will always perform fixed transitions from one specific number to the next, based on the "intrinsic properties of Random's algorithm". For example, if you see the number 553, you will always know that the next one will be 1347421470. How? Examine this code:

using System;
class App {
    static void Main() {
        Random r = new Random(553);
        Console.WriteLine(r.Next());
    }
}

Run this code and the output is 1347421470. This difficulty may also be due to the mechanics of the system clock. The system clock is continuously changing in value, so using a parameterless constructor will therefore initiate a different numerical sequence every time it is called up. However, since the clock has finite resolution, using the parameterless constructor to create different Random() objects in close succession can create random number generators that produce identical randomized numerical sequences. This problem can be avoided by creating one Random() object to generate many random numbers over time, instead of repeatedly creating several new Random() objects to generate one random number at a time. More to the point, if you're creating two Random objects, one after the other, they could actually end up in the same time-based seed.

However, some of these features of the random number generator can have somewhat of a practical usage. For example, if you want to repeat the same sequence of numbers, you can set the seed state during instantiation by passing the same integer value to the constructor. Once this Random() object has been created, we can call the Next() method to produce a random number. The Next() method can be overloaded in three different ways. Without any input parameters, the Next() method returns a random number anywhere from 0 to the maximum value of int32.Max, which is 2,147,483,647. The Next(int32) method returns a nonnegative random number from 0 to the Int32 integer value specified by the single input parameter. Lastly, the Next(Int32,Int32) method returns a random number from anywhere within the allowed Int32 integer range specified by the two input parameters. The Random.NextBytes() method fills the elements of a specified array of bytes with random bytes selected anywhere from 0 to 255. Therefore, the Random() class can also be used to populate a byte array with random bytes. Having said that, let's examine some sample test code:

using System;
public class App {
    public static void Main()
    {
        int seed = 345;
        int min = -44;
        int max = 30;
        Console.WriteLine("Testing 6 random Int32 from 0 to Int32.MAX");
        Random r1 = new Random(seed);
        for (int j = 0; j < 6; j++)
            Console.Write("{0,11} ", r1.Next());
        Console.WriteLine("Testing 6 random int32 from 0 to 30");
        Random r2 = new Random(seed);
        for (int j = 0; j < 6; j++)
            Console.Write("{0,11} ", r2.Next(max));
        Console.WriteLine("Testing 6 random int32 from -44 to 30");
        Random r3 = new Random(seed);
        for (int j = 0; j < 6; j++)
            Console.Write("{0,11} ", r3.Next(min, max));
        Console.WriteLine("Testing 5 random bytes: 0 to 255");
        Random r4 = new Random();
        Byte[] b = new Byte[10];
        r4.NextBytes(b);
        Console.WriteLine("The Random bytes are: ");
        for (int i = 0; i < 10; i++)
        {
            Console.Write(i);
            Console.Write(":");
            Console.WriteLine(b[i]);
        }
        Console.WriteLine("Testing 6 random doubles from 0 to 1");
        Random r5 = new Random(seed);
        for (int j = 0; j < 6; j++)
            Console.WriteLine("{0,11} ",r5.NextDouble());
        Console.WriteLine("Testing 6 random doubles from -44 to 30");
        Random r6 = new Random(seed);
        for (int j = 0; j < 6; j++)
            Console.WriteLine("{0,11}",(min+(max-min)*r6.NextDouble()));
    }
}

The output of this code is:

Testing 6 random Int32 from 0 to Int32.MAX
 2067976641   100391485  1973278494   420847188  2080081379   115165468 Testing
6 random int32 from 0 to 30
         28           1          27           5          29           1 Testing
6 random int32 from -44 to 30
         27         -41          23         -30          27         -41 Testing
5 random bytes: 0 to 255
The Random bytes are:
0:226
1:229
2:112
3:209
4:255
5:43
6:96
7:12
8:76
9:58
Testing 6 random doubles from 0 to 1
0.962976665218816
0.0467484281616045
0.918879404160604
0.195972243415179
0.968613373101043
0.0536281001072508
Testing 6 random doubles from -44 to 30
27.2602732261924
-40.5406163160413
23.9970759078847
-29.4980539872768
27.6773896094772
-40.0315205920634

Creating Random() objects successively can produce results if you work around the issues involved with the system clock and the deterministic algorithm. If you require a strong cryptographically sound random number generator when working with cryptography algorithms, the System.Security.Cryptography.RandomNumberGenerator class implements such an algorithm. Examine this code:

using System;
using System.Security.Cryptography;
class Program {
    static void Main(string[] args) {
        // create a new number generator
        RandomNumberGenerator rng = RandomNumberGenerator.Create();
        // define a byte array to fill with random data
        byte[] randomData = new byte[50];
        // generate random data
        rng.GetBytes(randomData);
        // print out the data
        Console.WriteLine(BitConverter.ToString(randomData));
        // wait for input before exiting
        Console.WriteLine("Press enter to finish");
        Console.ReadLine();
    }
}

The class is abstract but offers a static factory method Create() that returns a new RandomNumberGenerator instance. Here is the output of this code:

C1-38-8F-EB-1E-74-BA-E4-59-47-06-B3-BA-97-2C-91-0A-8D-B4-11-82-8C-48-84-AD-E6-D7
-C9-23-AE-AE-1A-F4-1C-D4-59-8B-E0-64-1B-50-7F-52-2E-DB-90-0B-91-F0-8E
Press enter to finish

Random Password Generation

For the sake of argument, let's assume that passwords are only generated via alphanumeric characters. There are 26 letters in the alphabet. The lower and upper case letters means total to 52 characters. The numbers 0 - 9 total 10, to make the overall total 62 characters. That makes for a long string declaration, but let's try it:

using System;
using System.Threading;
public  class App {
    private static string MakePassword(int pl)
    {
        string possibles = "abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNOPQRSTUVWXYZ0123456789";
        char[] passwords = new char[pl];
        Random rd = new Random();

        for (int i = 0; i < pl; i++)
        {
            passwords[i] = possibles[rd.Next(0, possibles.Length)];
        }
        return new string(passwords);
    }

    public static void Main()
    {
        Console.WriteLine("Slow Test for Random Password Generation");
        for (int i = 0; i < 10; i++)
        {
            Console.WriteLine("Password {0}={1}",i, MakePassword(10));
            Thread.Sleep(2000);
        }
        Console.WriteLine("Press the Enter Key to finish...");
        Console.ReadLine();
    }
}

Note: The above code snippets should be written to parallelize the loops, but the focus of this article is to examine random number generation. Once we have a firm grasp on that problem, then we can look at the code and locate what code blocks can be parallelized and with what type of parallelism construct. Here is the output of the above code:

Slow Test for Random Password Generation
Password 0=27OO8zn8Fh
Password 1=auaexRRxAc
Password 2=O8eUn0OqDv
Password 3=VuBmMhhOyr
Password 4=z9E1BrdHAJ
Password 5=Gv1sZJJ5vE
Password 6=OSoUo0ctrA
Password 7=swszda8ntT
Password 8=zSP1CsDLoO
Password 9=cwSFsBzEr6
Press the Enter Key to finish...

A Controversial Random Number Generator: The Mersenne Twister

The code given below has been referenced from snippets of the Mersenne Twister random number generator algorithm. This random number generator has received some criticism by the academic and scientific communities because the code is complex. At the same time, it is esteemed to be a powerful program. The reader can download the code in C or C++. Here is a C# version that has been edited to make it compile:

using System;
public class MersenneTwister
// Class MersenneTwister generates random numbers
// from a uniform distribution using the Mersenne
// Twister algorithm.
private const int N = 624;
private const int M = 397;
private const uint MATRIX_A = 0x9908b0dfU;
private const uint UPPER_MASK = 0x80000000U;
private const uint LOWER_MASK = 0x7fffffffU;
private const int MAX_RAND_INT = 0x7fffffff;
private uint[] mag01 = {0x0U, MATRIX_A};
private uint[] mt = new uint[N];
private int mti = N+1;
public MersenneTwister()
{ init_genrand( (uint)DateTime.Now.Millisecond); }
public MersenneTwister( int seed )
{
    init_genrand( (uint)seed );
}

public MersenneTwister( int[] init )
{
    uint[] initArray = new uint[init.Length];
    for ( int i = 0; i < init.Length; ++i )
    initArray[i] = (uint)init[i];
    init_by_array( initArray, (uint)initArray.Length);
}
public static int MaxRandomInt
{ get { return 0x7fffffff; } }
public int Next()
{ return genrand_int31(); }
public int Next( int maxValue )
{ return Next( 0, maxValue ); }
public int Next( int minValue, int maxValue )
{
    if ( minValue > maxValue )
    {
        int tmp = maxValue;
        maxValue = minValue;
        minValue = tmp;
    }
    return (int)(Math.Floor((maxValue-minValue+1)*genrand_real1()+
    minValue));
}
public float NextFloat()
{ return (float) genrand_real2(); }
public float NextFloat( bool includeOne )
{
    if ( includeOne )
    {
        return (float) genrand_real1();
    }
    return (float) genrand_real2();
}
public float NextFloatPositive()
{ return (float) genrand_real3(); }
public double NextDouble()
{ return genrand_real2(); }
public double NextDouble( bool includeOne )
{
    if ( includeOne )
    {
        return genrand_real1();
    }
    return genrand_real2();
}

public double NextDoublePositive()
{ return genrand_real3(); }
public double Next53BitRes()
{ return genrand_res53(); }
public void Initialize()
{ init_genrand((uint)DateTime.Now.Millisecond); }
public void Initialize( int seed )
{ init_genrand( (uint)seed ); }
public void Initialize( int[] init )
{
    uint[] initArray = new uint[init.Length];
    for ( int i = 0; i < init.Length; ++i )
    initArray[i] = (uint)init[i];
    init_by_array( initArray, (uint)initArray.Length );
}
private void init_genrand( uint s)
{
    mt[0]= s & 0xffffffffU;
    for (mti=1; mti<N; mti++)
    {
        mt[mti] = (uint)(1812433253U*(mt[mti-1]^(mt[mti-1]>>30))+mti);
        mt[mti] &= 0xffffffffU;
    }
}
private void init_by_array(uint[] init_key, uint key_length)
{
    int i, j, k;
    init_genrand(19650218U);
    i=1; j=0;
    k = (int)(N>key_length ? N : key_length);
    for (; k>0; k--)
    {
        mt[i] = (uint)((uint)(mt[i]^((mt[i-1]^(mt[i-1]>>30))*1664525U))+init_key[j]+j);
        mt[i] &= 0xffffffffU;
        i++; j++;
        if (i>=N) { mt[0] = mt[N-1]; i=1; }
        if (j>=key_length) j=0;
    }
    for (k=N-1; k>0; k--)
    {
        mt[i] = (uint)((uint)(mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) *
        1566083941U))- i);
        mt[i] &= 0xffffffffU;
        i++;
        if (i>=N) { mt[0] = mt[N-1]; i=1; }
    }
    mt[0] = 0x80000000U;
}

uint genrand_int32()
{
    uint y;
    if (mti >= N)
    {
        int kk;
        if (mti == N+1)
        init_genrand(5489U);
        for (kk=0;kk<N-M;kk++)
        {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        for (;kk<N-1;kk++)
        {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
        mti = 0;
    }
    y = mt[mti++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680U;
    y ^= (y << 15) & 0xefc60000U;
    y ^= (y >> 18);
    return y;
}
private int genrand_int31()
{ return (int)(genrand_int32()>>1); }
double genrand_real1()
{ return genrand_int32()*(1.0/4294967295.0); }
double genrand_real2()
{ return genrand_int32()*(1.0/4294967296.0); }
double genrand_real3()
{
    return (((double)genrand_int32())+0.5)*(1.0/4294967296.0);}
    double genrand_res53()
    {
        uint a=genrand_int32()>>5, b=genrand_int32()>>6;
        return(a*67108864.0+b)*(1.0/9007199254740992.0);
    }
}
public class Program {
    static void Main()
    {
        MersenneTwister randGen = new MersenneTwister();
        Console.WriteLine( "100 uniform random integers in [0,{0}]:",
        MersenneTwister.MaxRandomInt);
        int i;

        for (i = 0; i < 100; ++i)
        {
            Console.Write("{0} ",randGen.Next());
            if ( i%5 == 4 ) Console.WriteLine("");
        }
        Console.WriteLine("100 uniform random doubles in [0,1]:");
        for ( i = 0; i < 100; ++i )
        {
            Console.Write("{0} ",randGen.NextDouble().ToString("F8"));
            if ( i%5 == 4 ) Console.WriteLine("");
        }
        Console.WriteLine("Press ENTER to quit");
        Console.ReadLine();
    }
}

Here is the output:

100 uniform random integers in [0,2147483647]:
1075176619 857754206 1005167141 991201697 1075422282
1747626860 320357673 932416052 1761533440 1877355339
690124008 394204523 1673263413 1306605477 1750371637
131189303 31787654 55688665 488723751 172092270
1528431908 2143696765 1763326522 570125855 1703653473
1943673222 1063468238 979779157 1203824982 2138479727
1105805415 51695726 616356430 1907769139 403919762
546097329 732304019 1426151751 571894936 1787565766
435528614 2053456611 875459441 1223172521 1119364174
641508640 18152413 91285243 2068336737 1782242804
1847854439 1426078730 1696565377 220195592 1615216442
1311150674 2016878752 1411646858 2113603839 387896851
182685019 452901650 1143849234 1947560626 1623179537
1793681409 666445687 455322196 1485561736 2016878799
419516289 1492722441 1834382965 1304567204 940786356
159127256 1362751565 668535681 599232874 816298036
1449977427 1771450370 824382733 1749254406 456991468
1189135967 362909535 111507413 949147242 1370981469
1984562805 1397068659 1697759068 1093507400 691950388
2036212955 9845334 610019413 1477955157 1158880977
100 uniform random doubles in [0,1]:
0.64427878 0.58951317 0.40004608 0.76980695 0.00424254
0.21054363 0.57517565 0.89644978 0.22379096 0.67868496
0.85624201 0.02531357 0.79852453 0.38303446 0.73290709
0.75898620 0.88415779 0.38217626 0.56409770 0.37470631
0.65536917 0.48810426 0.05990990 0.38777581 0.80498216
0.32344267 0.78534319 0.09117531 0.95645391 0.62211520
0.47396311 0.88660040 0.72666519 0.62785680 0.67998362
0.06089570 0.66838163 0.61557270 0.05300447 0.80103798
0.60875345 0.88096833 0.33373527 0.95487843 0.93682441
0.84364382 0.00884743 0.07577453 0.92769417 0.05884617
0.21523187 0.15010924 0.54033703 0.83325611 0.49797325
0.04532573 0.65437883 0.63682698 0.76614741 0.82909524
0.84164811 0.21053670 0.27436116 0.23372914 0.47964557
0.34993759 0.71205157 0.93345212 0.24736210 0.88091276
0.65001251 0.04091075 0.81341497 0.88265975 0.69665167
0.81644969 0.63767136 0.53178586 0.89998561 0.39706215
0.47618763 0.15616494 0.19274149 0.46349037 0.49884292
0.99134203 0.00503471 0.97789549 0.74999581 0.79177777
0.35976462 0.90491676 0.02709002 0.01703469 0.28894546
0.96114512 0.71049253 0.89851955 0.61757205 0.15242437
Press ENTER to quit

Two raised to the 31^st power is 2147483647. The above algorithm was able to generate 100 random integers that fall within the range of 0 to 2147483647. The latter section was able to generate 100 double values between the range of 0 and 1. In conclusion, random number generation plays an integral part of certain applied mathematical fields. For a .NET developer, however, it might be safer to use the classes contained in the System.Security.Cryptography namespace.