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?

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