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

## Recursive Solution

// returns a evenly distributed random BigInteger from 1 to N.
BigInteger randomBigInteger(BigInteger N) {
if (N < Int32.MaxValue) {
return rand.Next((int)N);
} else {
return rand.Next() + (randomBigInteger(N >> 31) << 31);
}
}

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