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

.net, biginteger, c#, random, system.numerics

Solution

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.

Problem

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`?

Original source

Related problems