Miller-Rabin原始性測試通常返回素數的複合

-1

我一直試圖從零開始（僅用於基元和字符串）實現64位整數（長整數）的Miller-Rabin素數測試。我已經嘗試了來自Wikipedia的Java和僞代碼，以及其他各種網站。到目前爲止，只有非常小的數字才能正常工作。大多數數字都被錯誤地標記爲複合，例如53或101.我試圖跟蹤代碼的各個部分以查看問題出在哪裏。它似乎在最內層的循環中。我不知道具體問題是什麼。任何幫助表示讚賞。謝謝！Miller-Rabin原始性測試通常返回素數的複合

這裏是我的代碼：

public class PrimeTest 
{ 
public static void main(String[] args) 
{ 
    PrimeTest app = new PrimeTest(); 
} 

private PrimeTest() 
{ 
    long n = 53; // Change to any number. 53 is prime, but is reported as composite 
    if (checkPrime(n, 10)) 
    { 
     System.out.println(n + " is prime."); 
    } 
    else 
    { 
     System.out.println(n + " is not prime."); 
    } 
} 

// Check if n is prime with 4^(-k) change of error 
private boolean checkPrime(long n, int k) 
{ 
    // Factor n-1 as d*2^s 
    long d = n - 1; 
    int s = 0; 
    while (d % 2 == 0) 
    { 
     d /= 2; 
     s++; 
    } 

    // Repeat k times for 4^-k accuracy 
    for (int i = 0; i < k; i++) 
    { 
     long a = (long) ((Math.random() * (n - 3)) + 2); 
     long x = modPow(a, d, n); 
     if (x == 1 || x == (n - 1)) 
     { 
      continue; 
     } 
     int r; 
     for (r = 0; r < s; r++) 
     { 
      x = modPow(x, 2, n); 
      if (x == 1) 
      { 
       return false; 
      } 
      if (x == (n - 1)) 
      { 
       break; 
      } 
     } 
     if (r == s) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

// Return (base^exp) % mod 
private long modPow(long base, long exp, long mod) 
{ 
    if (mod == 1) 
    { 
     return 0; 
    } 
    long result = 1; 
    base = base % mod; 
    while (exp > 0) 
    { 
     if ((exp & 1) == 0) 
     { 
      result = (result * base) % mod; 
     } 
     exp = exp >> 1; 
     base = (base * base) % mod; 
     if (base == 1) 
     { 
      break; 
     } 
    } 
    return result; 
} 
}

來源

2017-12-03 Dominic Rutkowski

我已經downvoted這個問題，因爲有太多這裏有很多代碼。爲了清楚地說明問題的具體位置，請刪除不直接導致問題的任何代碼，如果可以將其減少到十行或更少，我會考慮收回downvote。請參閱：[如何創建最小，完整和可驗證示例]（http://stackoverflow.com/help/mcve）和[如何調試小程序]（https://ericlippert.com/2014/03/05 /如何調試的小程序/） –

這條線modPow：

if ((exp & 1) == 0)

是錯誤的，而應該是

if ((exp & 1) == 1)

來源

2017-12-03 16:27:38

Miller-Rabin原始性測試通常返回素數的複合

回答

相關問題