How can I generate a random BigInteger within a certain range?

Question

Consider this method that works well:

public static bool mightBePrime(int N) {
    BigInteger a = rGen.Next (1, N-1);
    return modExp (a, N - 1, N) == 1;
}

Now, in order to fulfill a requirement of the class I'm taking, mightBePrime must accept a BigInteger N, but that means that I need a different way to generate my random BigInteger a.

My first idea was to do something like BigInteger a = (N-1) * rGen.NextDouble (), but a BigInteger can't be multiplied by a double.

How can I generate a random BigInteger between 1 and N-1, where N is a BigInteger?

Solution 1

Here is a NextBigInteger extension method for the Random class. It is based on the excellent Fabio Iotti's implementation, modified for succinctness.

/// <summary>
/// Returns a random BigInteger that is within a specified range.
/// The lower bound is inclusive, and the upper bound is exclusive.
/// </summary>
public static BigInteger NextBigInteger(this Random random,
    BigInteger minValue, BigInteger maxValue)
{
    if (minValue > maxValue) throw new ArgumentException();
    if (minValue == maxValue) return minValue;
    BigInteger zeroBasedUpperBound = maxValue - 1 - minValue; // Inclusive
    Debug.Assert(zeroBasedUpperBound.Sign >= 0);
    byte[] bytes = zeroBasedUpperBound.ToByteArray();
    Debug.Assert(bytes.Length > 0);
    Debug.Assert((bytes[bytes.Length - 1] & 0b10000000) == 0);

    // Search for the most significant non-zero bit
    byte lastByteMask = 0b11111111;
    for (byte mask = 0b10000000; mask > 0; mask >>= 1, lastByteMask >>= 1)
    {
        if ((bytes[bytes.Length - 1] & mask) == mask) break; // We found it
    }

    while (true)
    {
        random.NextBytes(bytes);
        bytes[bytes.Length - 1] &= lastByteMask;
        var result = new BigInteger(bytes);
        Debug.Assert(result.Sign >= 0);
        if (result <= zeroBasedUpperBound) return result + minValue;
    }
}

The percentage of BigInteger instances that are discarded, in order to return a value within the desirable range, is 30% on average (best case 0%, worst case 50%).

The distribution of random numbers is uniform.

Usage example:

Random random = new();
BigInteger value = random.NextBigInteger(BigInteger.Zero, new BigInteger(1000));

---

Note: The structure of the bytes returned from the BigInteger.ToByteArray is well documented (in the Remarks section), so it should be fairly safe to assume that the BigInteger's byte[] representation is not going to change in future versions of the .NET platform. In case that happened, the above NextBigInteger implementation could fail in nasty ways, like entering an infinite loop or generating numbers within a wrong range. I've added some debugging assertions that should never fail with the current representation, but the coverage of checking for invalid conditions is by no means thorough.

Solution 2

Paul suggested in a comment that I generate a number using random bytes, then throw it away if it's too big. Here's what I came up with (Marcel's answer + Paul's advice):

public static BigInteger RandomIntegerBelow(BigInteger N) {
    byte[] bytes = N.ToByteArray ();
    BigInteger R;

    do {
        random.NextBytes (bytes);
        bytes [bytes.Length - 1] &= (byte)0x7F; //force sign bit to positive
        R = new BigInteger (bytes);
    } while (R >= N);

    return R;
}

http://amirshenouda.wordpress.com/2012/06/29/implementing-rsa-c/ helped a little too.

Solution 3

Use the Random-Class

public BigInteger getRandom(int length){
    Random random = new Random();
    byte[] data = new byte[length];
    random.NextBytes(data);
    return new BigInteger(data);
}

Solution 4

The naive implementation will fail on average 64 times before finding a valid BigInteger within the specified range.

On the worst case, my implementation will retry on average only 0.5 times (read as: 50% of the times it will find a result on the first try).

Also, unlike with modular arithmetic, my implementation maintains a uniform distribution.

Explanation

We must generate a random BigInteger between min and max.

1. If min > max, we swap min with max
2. To simplify the implementation we shift our range from [min, max] to [0, max-min], this way we won't have to deal with the sign bit
3. We count how many bytes max contains (bytes.Length)
4. From the most significant bit, we count how many bits are 0 (zeroBits)
5. We generate a random sequence of bytes.Length bytes
6. We know that for our sequence to be < max, at least zeroBits bits from the most significant bit must be 0, so we use a zeroBitMask to set them with a single bit-to-bit & operation over the most significant byte, this will save a lot of time by reducing the change of generating a number out of our range
7. We check if the number we generated is > max, and if so we try again
8. We unshift the range back from [0, max-min] to [min, max] by adding min to our result

And we have our number. 😊

Implementation

public static BigInteger RandomInRange(RandomNumberGenerator rng, BigInteger min, BigInteger max)
{
    if (min > max)
    {
        var buff = min;
        min = max;
        max = buff;
    }

    // offset to set min = 0
    BigInteger offset = -min;
    min = 0;
    max += offset;

    var value = randomInRangeFromZeroToPositive(rng, max) - offset;
    return value;
}

private static BigInteger randomInRangeFromZeroToPositive(RandomNumberGenerator rng, BigInteger max)
{
    BigInteger value;
    var bytes = max.ToByteArray();

    // count how many bits of the most significant byte are 0
    // NOTE: sign bit is always 0 because `max` must always be positive
    byte zeroBitsMask = 0b00000000;

    var mostSignificantByte = bytes[bytes.Length - 1];

    // we try to set to 0 as many bits as there are in the most significant byte, starting from the left (most significant bits first)
    // NOTE: `i` starts from 7 because the sign bit is always 0
    for (var i = 7; i >= 0; i--)
    {
        // we keep iterating until we find the most significant non-0 bit
        if ((mostSignificantByte & (0b1 << i)) != 0)
        {
            var zeroBits = 7 - i;
            zeroBitsMask = (byte)(0b11111111 >> zeroBits);
            break;
        }
    }

    do
    {
        rng.GetBytes(bytes);

        // set most significant bits to 0 (because `value > max` if any of these bits is 1)
        bytes[bytes.Length - 1] &= zeroBitsMask;

        value = new BigInteger(bytes);

        // `value > max` 50% of the times, in which case the fastest way to keep the distribution uniform is to try again
    } while (value > max);

    return value;
}

Test

using (var rng = RandomNumberGenerator.Create())
{
    BigInteger min = 0;
    BigInteger max = 5;

    var attempts = 10000000;
    var count = new int[(int)max + 1];

    var sw = Stopwatch.StartNew();

    for (var i = 0; i < attempts; i++)
    {
        var v = BigIntegerUtils.RandomInRange(rng, min, max);
        count[(int)v]++;
    }

    var time = sw.Elapsed;
    Console.WriteLine("Generated {0} big integers from {1} to {2} in {3}", attempts, min, max, time);
    Console.WriteLine("On average: {0} ms/integer or {1} integers/second", time.TotalMilliseconds / attempts, attempts / time.TotalSeconds);

    for (var i = 0; i <= max; i++)
        Console.WriteLine("{0} generated {1}% of the times ({2} times)", i, count[i] * 100d / attempts, count[i]);
}

Test output on my i7-6500U:

Generated 10000000 big integers from 0 to 5 in 00:00:09.5413677
On average: 0.00095413677 ms/integer or 1048067.77334449 integers/second
0 generated 16.66633% of the times (1666633 times)
1 generated 16.6717% of the times (1667170 times)
2 generated 16.66373% of the times (1666373 times)
3 generated 16.6666% of the times (1666660 times)
4 generated 16.68271% of the times (1668271 times)
5 generated 16.64893% of the times (1664893 times)

Another test output on my i7-6500U

Generated 10000000 big integers from 0 to 10^100 in 00:00:17.5036570
On average: 0.0017503657 ms/integer or 571309.184132207 integers/second

View more solutions

Comments

[spender]

How is a BigInteger an array (byte[])? This won't even compile. Perhaps you meant return new BigInteger(data)?

[masinger]

Sorry, my fault. I forgot that line.

[Trevor Dixon]

This doesn't ensure it's within the range I care about, but it's close. I'll generate a random number using this method, and if it's not in my range, I'll throw it away and try again.

[Rasmus Faber]

If this becomes too slow (in the worst case you would have to generate on average 256 values before you find one in the range), an alternative is to generate a larger number and return the remainder when dividing it with N. It will not be completely uniformly random, but the larger a number you generate (before dividing and taking remainder) the closer it gets to uniformly random.

[svick]

Why are you generating one more byte than necessary? Also, I think that using a do-while loop would make the code more DRY.

[Trevor Dixon]

To answer your question, see stackoverflow.com/a/5649264/711902. "You can make sure any BigInteger created from a byte[] is unsigned if you append a 00 byte to the end of the array before calling the constructor." I'm generating one extra byte, then setting the last to 0. If I don't generate that extra byte, my max possible random integer is less than N. I forgot about do-while. I'll do that instead.

[svick]

@TrevorDixon Another approach would be just to reset the highest bit and not a whole byte: bytes[bytes.Length - 1] &= (byte)0x7F;. If you do that, you don't need the additional byte.

[Trevor Dixon]

Oh good call. Thank you. Clearly I don't fully understand how these numbers are represented.

[Jim Mischel]

Two problems: 1) Range only allows integer parameters. 2) Even if Range allowed BigInteger, this returns a sequence of all values in the range, in order. He wants a random number in the range from <= value < to.

[pkuderov]

what about just take a Mod from it. Let's say you need number from a to b and this func returned x. You just need a + x.Abs().Mod(b - a). It's possible for BigInteger implementation in c#

[Christoph]

I would store the highest byte of the input value Int32 highestByteIndex = bytes.Length - 1; Int32 highestByte = bytes[highestByteIndex]; and in case the number is too high, only recalculate the highest byte like this in a first try: if (bytes[highestByteIndex] > highestByte) { bytes[highestByteIndex] = (Byte)_Random.Next(highestByte + 1); } and only if the number is still too high loop and recalculate the whole number.

[Trevor Dixon]

Cool! Can you add a paragraph explaining how it works, especially in contrast with the current accepted answer?

[Fabio Iotti]

Oops! I tried to explain the code with comments, but an overview is probably necessary. I'll be adding it ASAP.

[Matthew van Eerde]

Consider N = 128. N.ToByteArray() is [0x80, 0x00]. It adds the second byte to force the sign bit to be 0. System.Random.NextBytes() is going to return two random bytes [Y, X]. Even with clearing the top bit of X, it's going to be too large 127/128 of the time. Even then, Y is going to be too large half the time. Net result: we're going to have to loop on average 256 times before we slip under N. Clear the sign bit, but also clear those bits of the most significant randomly generated byte which are of higher order than the most significant 1 bit in N.