如何生成一定范围内的随机BigInteger?

问题描述

考虑这种方法效果很好:

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

现在，为了满足我所上课的要求， mightBePrime 必须接受 BigInteger N，但这意味着我需要一种不同的方法生成我的随机BigInteger a.

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.

我的第一个想法是做类似 BigInteger a =(N-1)* rGen.NextDouble()的事情，但是BigInteger不能乘以两倍.

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

如何生成1到N-1之间的随机BigInteger，其中N是BigInteger?

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

推荐答案

Paul在评论中建议我使用随机字节生成一个数字，如果数字太大，则将其丢弃.这是我想出的(Marcel的答案+ Paul的建议):

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/也有帮助.

这篇关于如何生成一定范围内的随机BigInteger?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！