Miller-Rabin原始性测试通常返回素数的复合

Z时代
2024-01-10
分类：问答

我一直试图从零开始（仅用于基元和字符串）实现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; 
} 
}