Java BigInteger素数

Question

我正在尝试生成BigInteger类型的随机素数，即我提供的最小值和最大值之间。

我知道BigInteger.probablePrime（int bitlength，random），但我不确定比特长度是如何转换为输出素数的最大值/最小值。

谢谢， Steven1350

Answer 1

BigInteger.probablePrime（bitLength，random）将返回指定位长度的（可能）素数。这转换为最大值2 ^比特长度-1和最小值2 ^（比特长度-1）。尽管我讨厌它作为答案，但它可能是你最好的选择，除非你想开始钻研数论。

你需要做的是找出你的范围所要求的位长，然后将它们传递给 probablePrime（），直到你找到一个在正确范围内的素数。

Answer 2

如果您的比率max / min不接近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);

密度为素数总体上相当高，它在log（x）中基本上是1，所以你不必重复太多次来找到素数。 （举个例子：对于大约10个 ²³ 的数字，平均每52个整数中就有一个是素数。上面的代码只有6个数字中的2个，所以你最终对于大约10 ²³ 的数字，平均循环17次。）

确保你有一个很好的素性测试，而Java BigInteger有一个。

作为读者的练习，扩展上述功能，以便通过使用30k + x（模30，有22个总是复合的模数，只剩下8个可能是素数）提前滤除更多的复合数。 ，或210k + x。

编辑：另请参阅美国专利＃7149763 （OMFG !!!）