**This is an old revision of the document!**

# 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.

## Best Solution

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;
}

## Old Approach

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

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 ^{2)}

## Alternative Approach #2 - retry until number is less than N

Put your code to generate the random BigInteger in a loop and continue generating random BigIntegers until the random BigInteger is less than N.

BigInteger random_number = CreateRandomBigInteger(N);
while (N > random_number) {
random_number = CreateRandomBigInteger(N);
}

This will ensure that your random number distribution is even but could take a very long time with this code if N is a 33 bit integer.

Back to top