米勒 - 拉宾测试:我的代码中的错误

Question

我根据以下伪代码编写了一个Miller-Rabin素性测试:

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任务描述的一部分.

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

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

Answer 1

在这个声明中

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

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