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原始性测试通常返回素数的复合

回答

相关问题