Random Big Integers

C# does not provide a way to create a random BigInteger, so we have to create our own way by combining multiple random 32 bit integers.

static Random rand = new Random();

// returns a evenly distributed random BigInteger from 1 to N.
BigInteger randomBigInteger(BigInteger N) {
  BigInteger result = 0;
  do {
    int length = (int)Math.Ceiling(BigInteger.Log(N, 2));
    int numBytes = (int)Math.Ceiling(length / 8.0);
    byte[] data = new byte[numBytes];
    rand.NextBytes(data);
    result = new BigInteger(data);
  } while (result >= N || result <= 0);
  return result;
}

The first step is to determine the length of the max value you want (in bits). This can be done using the following code. ¹⁾

length = BigInteger.Log(N, 2)+1

Then we allocate a new big integer to hold the random number and generate enough random 32 bit integers to create a random number of at least length bits. We use the bit left bit shift operator to move over the random bits from the last iteration.

BigInteger random_number = 0;
for (int i = 0; i < length/31 + 1; i++)
    random_number = (random_number << 31) + rand.Next();

This likely creates a number much larger than N. For example if N is 40 bits, the loop would run 2 times and we would get a random 62 bit integer. So we need to shrink the integer so it's no bigger than N.

This is the easiest way, simply mod the random number by N as follows.

random_number %= N;

This however can create uneven distributions if N and the largest value of random_number are similar ²⁾

We have made a program that has both methods of generating BigIntegers and draws the distribution of the randomly generated numbers. In the program you can select “mod” to see BigIntegers generated by simply modding, and then by selecting “repeat” you will see the distribution when the random code is repeated until a number in the desired range is obtained. It also shows you the time required to generate all the numbers so you can get a sense for the difference in performance.

Download RandomBigIntegers C# Project