Java BigInteger 素数

Question

我正在尝试生成一个 BigInteger 类型的随机质数，它介于我提供的最小值和最大值之间。

我知道 BigInteger.probablePrime(int bitlength, random)，但我不确定位长如何或是否会转换为输出素数的最大/最小值。

谢谢，史蒂文1350

Answer 1

如果您的最大/最小比率不接近 1，jprete 的回答是可以的。

如果您的范围很窄，最好的选择可能就是执行以下操作:

// this is pseudocode:
//
// round min down to multiple of 6, max up to multiple of 6
min6 = floor(min/6);
max6 = ceil(max/6);
maybePrimeModuli = [1,5];
do 
{
   b = generateRandom(maybePrimeModuli.length);
   // generate a random offset modulo 6 which could be prime
   x = 6*(min6 + generateRandom(max6-min6)) + b;
   // generate a random number which is congruent to b modulo 6
   // from 6*min6 to 6*max6-1
   // (of the form 6k+1 or 6k+5)

   // the other choices 6k, 6k+2, 6k+3, 6k+4 are composite 
} while not isProbablePrime(x);

density of primes总的来说是相当高的，它基本上是 log(x) 中的 1，所以你不应该重复太多次来找到一个质数。 (举个例子:对于 10²³ 左右的数字，平均每 52 个整数中就有一个是素数。上面的代码只对每 6 个数字中的 2 个有问题，所以你最终会得到对于 10²³ 左右的数字，平均循环 17 次。)

只需确保您有一个良好的素数测试，而 Java BigInteger 有一个。

作为读者的练习，扩展上述函数，使其通过使用 30k + x 提前过滤掉更多合数(模 30，有 22 个模总是合数，剩下的 8 个可能是质数) , 或 210k + x。

编辑:另见 US patent #7149763 (我的天啊!!!)