如何在 Java 中生成一个随机的 BigInteger 值？

How to generate a random BigInteger value in Java?

提问by Bill the Lizard

I need to generate arbitrarily large random integers in the range 0 (inclusive) to n (exclusive). My initial thought was to call nextDoubleand multiply by n, but once n gets to be larger than 2⁵³, the results would no longer be uniformly distributed.

我需要在 0（含）到 n（不含）范围内生成任意大的随机整数。我最初的想法是调用nextDouble并乘以 n，但是一旦 n 大于 2 ⁵³，结果将不再均匀分布。

BigIntegerhas the following constructor available:

BigInteger有以下构造函数可用：

public BigInteger(int numBits, Random rnd)

Constructs a randomly generated BigInteger, uniformly distributed over the range 0 to (2^numBits- 1), inclusive.

构造一个随机生成的 BigInteger，均匀分布在 0 到 (2 ^numBits- 1)范围内，包括0 到 (2 ^numBits- 1)。

How can this be used to get a random value in the range 0 - n, where n is not a power of 2?

如何使用它来获得 0 - n 范围内的随机值，其中 n 不是 2 的幂？

采纳答案by Thomas Pornin

Use a loop:

使用循环：

BigInteger randomNumber;
do {
    randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);

on average, this will require less than two iterations, and the selection will be uniform.

平均而言，这将需要少于两次迭代，并且选择将是统一的。

Edit:If your RNG is expensive, you can limit the number of iterations the following way:

编辑：如果您的 RNG 很昂贵，您可以通过以下方式限制迭代次数：

int nlen = upperLimit.bitLength();
BigInteger nm1 = upperLimit.subtract(BigInteger.ONE);
BigInteger randomNumber, temp;
do {
    temp = new BigInteger(nlen + 100, randomSource);
    randomNumber = temp.mod(upperLimit);
} while (s.subtract(randomNumber).add(nm1).bitLength() >= nlen + 100);
// result is in 'randomNumber'

With this version, it is highly improbable that the loop is taken more than once (less than one chance in 2^100, i.e. much less than the probability that the host machine spontaneously catches fire in the next following second). On the other hand, the mod()operation is computationally expensive, so this version is probably slower than the previous, unless the randomSourceinstance is exceptionally slow.

在这个版本中，循环被多次采用是非常不可能的（小于2^100 中的一次机会，即远小于主机在下一秒自发着火的概率）。另一方面，该mod()操作在计算上很昂贵，所以这个版本可能比以前慢，除非randomSource实例特别慢。

回答by Jon Skeet

The simplest approach (by quite a long way) would be to use the specified constructor to generate a random number with the right number of bits (floor(log2 n) + 1), and then throw it away if it's greater than n. In the worst possible case (e.g. a number in the range [0, 2ⁿ+ 1) you'll throw away just under half the values you create, on average.

最简单的方法（很长的路要走）是使用指定的构造函数生成一个具有正确位数 ( floor(log2 n) + 1)的随机数，然后在它大于 n 时将其丢弃。在最坏的情况下（例如，[0, 2 ⁿ+ 1范围内的数字），平均而言，您将丢弃不到一半的值。

回答by Bill the Lizard

The following method uses the BigInteger(int numBits, Random rnd)constructor and rejects the result if it's bigger than the specified n.

以下方法使用BigInteger(int numBits, Random rnd)构造函数，如果结果大于指定的 n，则拒绝结果。

public BigInteger nextRandomBigInteger(BigInteger n) {
    Random rand = new Random();
    BigInteger result = new BigInteger(n.bitLength(), rand);
    while( result.compareTo(n) >= 0 ) {
        result = new BigInteger(n.bitLength(), rand);
    }
    return result;
}

The drawback to this is that the constructor is called an unspecified number of times, but in the worst case (n is just slightly greater than a power of 2) the expected number of calls to the constructor should be only about 2 times.

这样做的缺点是构造函数被调用的次数未指定，但在最坏的情况下（n 仅略大于 2 的幂），对构造函数的预期调用次数应该只有大约 2 次。

回答by Riduidel

Why not constructing a random BigInteger, then building a BigDecimal from it ? There is a constructor in BigDecimal : public BigDecimal(BigInteger unscaledVal, int scale)that seems relevant here, no ? Give it a random BigInteger and a random scale int, and you'll have a random BigDecimal. No ?

为什么不构建一个随机的 BigInteger，然后从中构建一个 BigDecimal 呢？BigDecimal 中有一个构造函数：public BigDecimal(BigInteger unscaledVal, int scale)这在这里似乎很相关，不是吗？给它一个随机的 BigInteger 和一个随机的 scale int，你就会有一个随机的 BigDecimal。不 ？

回答by Chris Nash

Compile this F# code into a DLL and you can also reference it in your C# / VB.NET programs

将此 F# 代码编译为 DLL，您也可以在 C#/VB.NET 程序中引用它

type BigIntegerRandom() =
    static let internalRandom = new Random()

    /// Returns a BigInteger random number of the specified number of bytes.
    static member RandomBigInteger(numBytes:int, rand:Random) =
        let r = if rand=null then internalRandom else rand
        let bytes : byte[] = Array.zeroCreate (numBytes+1)
        r.NextBytes(bytes)
        bytes.[numBytes] <- 0uy
        bigint bytes

    /// Returns a BigInteger random number from 0 (inclusive) to max (exclusive).
    static member RandomBigInteger(max:bigint, rand:Random) =
        let rec getNumBytesInRange num bytes = if max < num then bytes else getNumBytesInRange (num * 256I) bytes+1
        let bytesNeeded = getNumBytesInRange 256I 1
        BigIntegerRandom.RandomBigInteger(bytesNeeded, rand) % max

    /// Returns a BigInteger random number from min (inclusive) to max (exclusive).
    static member RandomBigInteger(min:bigint, max:bigint, rand:Random) =
        BigIntegerRandom.RandomBigInteger(max - min, rand) + min

回答by Andy Turner

Here is how I do it in a class called Generic_BigInteger available via: Andy Turner's Generic Source Code Web Page

以下是我在一个名为 Generic_BigInteger 的类中如何做到这一点的： Andy Turner's Generic Source Code Web Page

/**
 * There are methods to get large random numbers. Indeed, there is a
 * constructor for BigDecimal that allows for this, but only for uniform
 * distributions over a binary power range.
 * @param a_Random
 * @param upperLimit
 * @return a random integer as a BigInteger between 0 and upperLimit
 * inclusive
 */
public static BigInteger getRandom(
        Generic_Number a_Generic_Number,
        BigInteger upperLimit) {
    // Special cases
    if (upperLimit.compareTo(BigInteger.ZERO) == 0) {
        return BigInteger.ZERO;
    }
    String upperLimit_String = upperLimit.toString();
    int upperLimitStringLength = upperLimit_String.length();
    Random[] random = a_Generic_Number.get_RandomArrayMinLength(
        upperLimitStringLength);
    if (upperLimit.compareTo(BigInteger.ONE) == 0) {
        if (random[0].nextBoolean()) {
            return BigInteger.ONE;
        } else {
            return BigInteger.ZERO;
        }
    }
    int startIndex = 0;
    int endIndex = 1;
    String result_String = "";
    int digit;
    int upperLimitDigit;
    int i;
    // Take care not to assign any digit that will result in a number larger
    // upperLimit
    for (i = 0; i < upperLimitStringLength; i ++){
        upperLimitDigit = new Integer(
                upperLimit_String.substring(startIndex,endIndex));
        startIndex ++;
        endIndex ++;
        digit = random[i].nextInt(upperLimitDigit + 1);
        if (digit != upperLimitDigit){
            break;
        }
        result_String += digit;
    }
    // Once something smaller than upperLimit guaranteed, assign any digit
    // between zero and nine inclusive
    for (i = i + 1; i < upperLimitStringLength; i ++) {
        digit = random[i].nextInt(10);
        result_String += digit;
    }
    // Tidy values starting with zero(s)
    while (result_String.startsWith("0")) {
        if (result_String.length() > 1) {
            result_String = result_String.substring(1);
        } else {
            break;
        }
    }
    BigInteger result = new BigInteger(result_String);
    return result;
}

回答by lpsun

Just use modular reduction

只需使用模块化缩减

new BigInteger(n.bitLength(), new SecureRandom()).mod(n)

回答by remon78eg

if we want to generate random 70 digits of biginteger we can generate array of byte[70] and fill it with random numbers from 0 to 9 and add 48 to make digit chars and convert the digit chars to biginteger

如果我们想生成 biginteger 的随机 70 位数字，我们可以生成 byte[70] 数组并用 0 到 9 的随机数填充它并添加 48 以制作数字字符并将数字字符转换为 biginteger

public BigInteger RandomBigInteger(int digits_len) {
    Random rnd = new Random();
    byte[]num = new byte[digits_len];
    if(digits_len>1){//first digit must not be 0 because 0555 will be 555
        num[0]=(byte)((((int)(rnd.nextFloat()*10))%9)+1+48);//([*10 means] rnd 0-9),([%9 means] 0-8 , [+1 means] 1-9) ,([+48 means] 0->48,1->49)
        for(int i=1;i<num.length;i++){ num[i]=(byte)((((int)(rnd.nextFloat()*10))%10)+48); }//([*10 means] rnd 0-9),([%10 means] 0-9 because rnd may be 1.000*10=10) ,([+48 means] 0->48,1->49)
    }else{//digits_len = 1 , it can be 0-9
        num[0]=(byte)((((int)(rnd.nextFloat()*10))%10)+48);//([*10 means] rnd 0-9),([%10 means] 0-9 because rnd may be 1.000*10=10) ,([+48 means] 0->48,1->49)
    }
    return new BigInteger(new String(num,StandardCharsets.ISO_8859_1),10);//convert the digit chars to biginteger
}

BigInteger num = RandomBigInteger(5);//num = 12345