Miller-Rabin Primality Test頻繁に素数のコンポジットを返します

Question

私は、64ビット整数（long）で機能するスクラッチ（プリミティブとストリングのみ）からMiller-Rabin素数テストを実装しようとしています。私はWikipediaからJavaと擬似コードだけでなく、他のさまざまなWebサイトを試してみました。これまでは、非常に小さな数字しか正しく機能していませんでした。ほとんどの数値は、53や101などの間違ってマークされたコンポジットです。私は、問題のどこにあるかを見るためにコードのさまざまなセクションを追跡しようとしました。それは一番内側のループのようです。私は特定の問題が何であるか分からない。どんな助けもありがとうございます。ありがとう！ここで

は私のコードです：

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; 
} 
} 

Answer 1

modPowでこの行：

if ((exp & 1) == 0) 

が間違っているとあまりにもありますので、代わりに私はこの質問をd​​ownvotedている

if ((exp & 1) == 1)