7

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

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

谢谢，史蒂文1350

4

2 回答 2

3

如果您的最大/最小比率不接近 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 23左右的数字，平均每 52 个整数中有一个是素数。上面的代码只对每 6 个数字中的 2 个感到困扰，所以你最终会平均循环 17 次10 23左右的数字。）

只要确保你有一个好的素数测试，Java BigInteger 就有一个。

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

编辑：另见美国专利#7149763（OMFG！！！）

于 2009-11-26T02:04:51.553 回答
2

BigInteger.probablePrime(bitLength, random)将返回指定位长度的（可能的）素数。这转化为最大值 2^bitlength - 1 和最小值 2^(bitlength - 1)。尽管我讨厌它作为答案，但除非您想开始研究数论，否则这可能是您最好的选择。

您需要做的是找出您的范围要求的位长度，然后将它们传递给您，probablePrime()直到您获得正确范围内的素数。

于 2009-11-26T01:14:03.497 回答