Java中的Miller-Rabin原始性測試

我目前正在研究Project Euler，並認爲如果不勉強強迫所有問題，它可能會更有趣（以及更好的學習體驗）。在問題3中，它要求一個數字的主要因素，我的解決方案是將數字分解（使用另一個分解算法），然後測試素數因子。我想出了一個Miller-Rabin Primality測試的代碼（在徹底研究素性測試之後），它對於我輸入的所有複合奇數都是正確的。任何人都可以幫我弄清楚爲什麼？我以爲我已經正確編碼了算法。Java中的Miller-Rabin原始性測試

public static boolean isPrime(long num) 
{ 
if(num % 2 == 0) 
    return false; 
else 
{ 
    double d; 
    int r=0; 
    while((num-1) % Math.pow(2,r+1) == 0) 
     r++; 
    d = (num-1) % Math.pow(2,r); 
    int[] a = {2,3,5,7,11,13,17,23,31,62,73,1662803}; 
    boolean primality = true; 
    for(int k = 0; k < a.length; k++) 
    { 
     if((Math.pow(a[k],d)-1) % num != 0) 
     { 
      for(int s = 0; s < r-1; s++) 
      { 
       if((Math.pow(a[k],Math.pow(2,s)*d)+1) % num != 0) 
        primality = false; 

      } 
     } 
    } 
    return primality; 
}

來源

2013-06-13 Juan Sebastian Lozano

你試過跟蹤代碼嗎？ –

這與你的代碼沒有關係，我也沒有多少專業知識，但「考慮數字（使用另一個代理算法）」是一個難以確定素數的問題。您可以通過獲取素數列表來避免蠻力強制分解。獲得素數列表的最簡單方法就是使用篩子。 – maybeWeCouldStealAVan

'Math.pow（a [k]，d）-1）％num' - 我會說你的雙打超出了他們可以表示範圍內的每個整數的範圍。 –

鑑於num > 3，您需要：d, r s.t. pow(2,r) * d = num - 1, where d is odd。

您正在有效計算從num - 1結尾的零，以去除2的因子。但是，在該循環之後，您知道pow(2,r)是因子num - 1。因此：

d = (num-1) % Math.pow(2,r);

總是會產生：d = 0。我懷疑你打算用/（div）代替%（mod）否則，Math.pow(a[k],d)-1將始終產生(0)，並且永遠不會執行內部循環。

正如其他人指出的，一些簡單的跟蹤語句或斷言會發現這些錯誤。我認爲你還有其他問題，比如整數溢出。對a[]候選人（a-SPRP測試）進行測試的循環看起來完全錯誤。

也許你已經從Wikipedia得到了算法，我在The Handbook of Applied Cryptography喜歡更詳細的參考：4.2.3：米勒 - 拉賓測試，算法：4.24。

來源

2013-06-13 11:41:34

謝謝你提供這個非常豐富的答案:)我會研究你提供的資源，因爲它們看起來非常有用，下一次會更仔細地使用trace語句（現在我知道它們是什麼）。 –

@JuanSebastianLozanoMuñoz - 因爲你正在經歷項目歐拉問題，所以我認爲你可能會發現一個有效的Miller-Rabin測試很有用，所以我在這裏有一小段代碼（http://pastebin.com/8GJC5s61）。 –

哇，非常感謝你:)這肯定會幫助我通過體育問題的方式。 –

Java中的Miller-Rabin原始性測試

回答

相關問題