Miller-Rabin Primality Test 종종 소수를위한 합성물을 반환합니다.

Question

저는 64 비트 정수 (long)에서 작동하는 처음부터 Miller-Rabin 소수 테스트를 구현하려고 시도해 왔습니다 (프리미티브 및 문자열 만). 나는 다양한 다른 웹 사이트뿐만 아니라 Wikipedia에서 자바와 의사 코드를 시도했다. 지금까지 아주 작은 숫자 만 제대로 작동했습니다. 대부분의 숫자는 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) 

잘못하고 너무 없기 때문에 대신 내가이 질문을 downvoted 한

if ((exp & 1) == 1)