d - 米勒-拉宾测试 : bug in my code

Question

我写了一个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 的伪代码的版本.

编辑:回复:溢出问题。我怀疑是这样的。我仍然很困惑为什么 Ruby 版本没有那个问题。它可能在引擎盖下以不同的方式处理它。如果我使用 BigInt，代码确实可以工作，但比我使用 modpow 时要慢很多。所以我想我无法摆脱它。很遗憾 Phobos 没有内置 modpow，或者我一定是忽略了它。

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

Answer 1

在这个声明中

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

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