Java BigInteger素數

Question

我想生成一個隨機的BigInteger類型的素數，即在我提供的最小值和最大值之間。

我知道BigInteger.probablePrime（int比特長度，隨機），但我不知道如何甚至如果比特長度轉換爲輸出素數的最大/最小值。

感謝， Steven1350

Answer 1

BigInteger.probablePrime(bitLength, random)是否會返回指定位長度的（可能的）黃金。這意味着最大值爲2^bitlength-1，最小值爲2 ^（bitlength-1）。儘管我討厭它作爲答案，但除非你想開始研究數論，否則這可能是你最好的選擇。

你需要做的是找出你的範圍要求的位長，然後將它們傳遞給probablePrime()，直到你找到一個在正確範圍內的素數。

Answer 2

jprete的回答是好的，如果你比最大值/最小值是不是接近1

如果你有一個狹窄的範圍內，最好的辦法是可能只是做類似如下：

// 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個有影響，所以你最終會平均循環17次次數約爲10 。）

只要確保您有一個良好的素性測試，並且Java BigInteger有一個。

作爲讀者的練習，擴展上述函數，以便通過使用30k + x提前過濾出更多的合成數字（模數爲30，總共有22個模數合成，只剩下8個可能爲素數），或210k + x。

編輯：另見US patent #7149763（OMFG !!!）