米勒 - 拉賓測試：錯誤在我的代碼

我已經寫了基於以下僞代碼Miller-Rabin primality test：米勒 - 拉賓測試：錯誤在我的代碼

Input: n > 2, an odd integer to be tested for primality; 
     k, a parameter that determines the accuracy of the test 
Output: composite if n is composite, otherwise probably prime 
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1 
LOOP: repeat k times: 
    pick a randomly in the range [2, n − 1] 
    x ← ad mod n 
    if x = 1 or x = n − 1 then do next LOOP 
    for r = 1 .. s − 1 
     x ← x2 mod n 
     if x = 1 then return composite 
     if x = n − 1 then do next LOOP 
    return composite 
return probably prime

我有很少的代碼獲得過去的31（如果我把它放在一個循環測試數字從2到100）。一定有什麼問題，但我看不到它是什麼。

bool isProbablePrime(ulong n, int k) { 
    if (n < 2 || n % 2 == 0) 
     return n == 2; 

    ulong d = n - 1; 
    ulong s = 0; 
    while (d % 2 == 0) { 
     d /= 2; 
     s++; 
    } 
    assert(2 ^^ s * d == n - 1); 
    outer: 
    foreach (_; 0 .. k) { 
     ulong a = uniform(2, n); 
     ulong x = (a ^^ d) % n; 
     if (x == 1 || x == n - 1) 
      continue; 
     foreach (__; 1 .. s) { 
      x = (x ^^ 2) % n; 
      if (x == 1) return false; 
      if (x == n - 1) continue outer; 
     } 
     return false; 
    } 
    return true; 
}

我也試着變體

... 

    foreach (__; 1 .. s) { 
     x = (x ^^ 2) % n; 
     if (x == 1) return false; 
     if (x == n - 1) continue outer; 
    } 
    if (x != n - 1) return false; // this is different 

    ...

我有不同的版本，正常工作的測試，但它使用modpow。我希望有一個更接近僞代碼的版本，它是rossetta.org task description的一部分。

編輯：Re：溢出問題。我懷疑這樣的事情。我仍然困惑爲什麼Ruby版本沒有這個問題。它可能在引擎蓋下以不同的方式處理它。如果我使用BigInt，代碼可以工作，但比使用modpow慢很多。所以我想我無法擺脫這一點。這是一個可惜的Phobos沒有內置的modpow，或者我一定忽略了它。

ulong x = ((BigInt(a) ^^ d) % BigInt(n)).toLong();

來源

2011-05-31 fwend

它看起來像Ruby沒有這個問題，因爲它會在即將發生的溢出時自動使用Bignum：http://www.ruby-doc.org/core/classes/Bignum.html – BCS 2011-05-31 21:01:19

在這份聲明中

ulong x = (a ^^ d) % n;

數量(a ^^ d)國防部操作之前可能溢出可能發生。 modpow版本不會遇到這個問題，因爲該算法避免了任意大的中間值的需要。

來源

2011-05-31 08:13:30

米勒 - 拉賓測試：錯誤在我的代碼

回答

相關問題