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

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.

Answer 2

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