d - Miller-Rabin 测试 : bug in my code

我已经根据以下伪代码编写了一个 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();

最佳答案

在这份声明中

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

在 mod 操作发生之前，(a ^^ d) 的数量可能已经溢出。 modpow 版本不会遇到这个问题，因为该算法避免了对任意大中间值的需要。

关于d - Miller-Rabin 测试 : bug in my code，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6184550/