C++中的Miller-Rabin素數測試問題

Question

我一直試圖實現the algorithm from wikipedia，雖然它從不輸出合成數字作爲素數，但它輸出的素數也是75％。

多達1000它給我此輸出素數：

3，5，7，11，13，17，41，97，193，257，641，769

據我知道，我的實現與僞代碼算法完全相同。我已經逐行調試它，它產生了所有預期的變量值（我跟隨着我的計算器）。這裏是我的功能：

bool primeTest(int n) 
{ 
    int s = 0; 
    int d = n - 1; 

    while (d % 2 == 0) 
    { 
     d /= 2; 
     s++; 
    } 

    // this is the LOOP from the pseudo-algorithm 
    for (int i = 0; i < 10; i++) 
    { 
     int range = n - 4; 
     int a = rand() % range + 2; 
     //int a = rand() % (n/2 - 2) + 2; 
     bool skip = false; 
     long x = long(pow(a, d)) % n; 

     if (x == 1 || x == n - 1) 
      continue; 

     for (int r = 1; r < s; r++) 
     { 
      x = long(pow(x, 2)) % n; 

      if (x == 1) 
      { 
       // is not prime 
       return false; 
      } 
      else if (x == n - 1) 
      { 
       skip = true; 
       break; 
      } 
     } 

     if (!skip) 
     { 
      // is not prime 
      return false; 
     } 
    } 

    // is prime 
    return true; 
} 

任何幫助，將不勝感激d：

編輯：這裏是整個程序，編輯爲你們提示 - 現在的產量更是破：

bool primeTest(int n); 

int main() 
{ 
    int count = 1;  // number of found primes, 2 being the first of course 
    int maxCount = 10001; 
    long n = 3; 
    long maxN = 1000; 
    long prime = 0; 

    while (count < maxCount && n <= maxN) 
    { 
     if (primeTest(n)) 
     { 
      prime = n; 
      cout << prime << endl; 
      count++; 
     } 

     n += 2; 
    } 

    //cout << prime; 
    return 0; 
} 

bool primeTest(int n) 
{ 
    int s = 0; 
    int d = n - 1; 

    while (d % 2 == 0) 
    { 
     d /= 2; 
     s++; 
    } 

    for (int i = 0; i < 10; i++) 
    { 
     int range = n - 4; 
     int a = rand() % range + 2; 
     //int a = rand() % (n/2 - 2) + 2; 
     bool skip = false; 
     //long x = long(pow(a, d)) % n; 
     long x = a; 
     for (int z = 1; z < d; z++) 
     { 
      x *= x; 
     } 

     x = x % n; 

     if (x == 1 || x == n - 1) 
      continue; 

     for (int r = 1; r < s; r++) 
     { 
      //x = long(pow(x, 2)) % n; 
      x = (x * x) % n; 

      if (x == 1) 
      { 
       return false; 
      } 
      else if (x == n - 1) 
      { 
       skip = true; 
       break; 
      } 
     } 

     if (!skip) 
     { 
      return false; 
     } 
    } 

    return true; 
} 

現在素數的輸出端，從3至1000（如前），是：

3，5，17，257

我現在看到x變得太大了，它變成了垃圾值，但直到我刪除了「％n」部分時纔看到它。問題

Answer 1

錯誤的可能來源是對pow函數的兩次調用。中間結果會很大（特別是對於第一次調用），並且可能會溢出，導致錯誤。您應該查看Wikipedia上的modular exponentiation主題。

Answer 2

來源可能是在這裏：

x = long(pow(x, 2)) % n; 

pow從浮點數C標準庫的工作方式，因此使用它是一個非常糟糕的主意，如果你只是想計算的權力n爲模。解決方案非常簡單，只需手動平方即可：

x = (x * x) % n