java - Miller-Rabin 素数性テストは素数の合成を返すことが多い

Question

私は、64 ビット整数 (long) で機能する Miller-Rabin primality テスト (プリミティブと文字列のみ) を最初から実装しようとしています。Java とウィキペディアの疑似コード、および他のさまざまな Web サイトを試しました。これまでのところ、正しく機能しているのは非常に少数です。ほとんどの数字は、53 や 101 など、複合として誤ってマークされています。コードのさまざまなセクションを追跡して、問題がどこにあるかを調べてみました。一番内側のループにあるようです。具体的な問題が何かわかりません。どんな助けでも大歓迎です。ありがとう！

これが私のコードです：

public class PrimeTest
{
public static void main(String[] args)
{
    PrimeTest app = new PrimeTest();
}

private PrimeTest()
{
    long n = 53; // Change to any number. 53 is prime, but is reported as composite
    if (checkPrime(n, 10))
    {
        System.out.println(n + " is prime.");
    }
    else
    {
        System.out.println(n + " is not prime.");
    }
}

// Check if n is prime with 4^(-k) change of error
private boolean checkPrime(long n, int k)
{
    // Factor n-1 as d*2^s
    long d = n - 1;
    int s = 0;
    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }

    // Repeat k times for 4^-k accuracy
    for (int i = 0; i < k; i++)
    {
        long a = (long) ((Math.random() * (n - 3)) + 2);
        long x = modPow(a, d, n);
        if (x == 1 || x == (n - 1))
        {
            continue;
        }
        int r;
        for (r = 0; r < s; r++)
        {
            x = modPow(x, 2, n);
            if (x == 1)
            {
                return false;
            }
            if (x == (n - 1))
            {
                break;
            }
        }
        if (r == s)
        {
            return false;
        }
    }
    return true;
}

// Return (base^exp) % mod
private long modPow(long base, long exp, long mod)
{
    if (mod == 1)
    {
        return 0;
    }
    long result = 1;
    base = base % mod;
    while (exp > 0)
    {
        if ((exp & 1) == 0)
        {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
        if (base == 1)
        {
            break;
        }
    }
    return result;
}
}