Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
478 views
in Technique[技术] by (71.8m points)

c# - How can I generate a random BigInteger within a certain range?

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...