Miller Rabin - 0.5 的錯誤機率有可能嗎？

我正在測試 Miller Rabin 的屬性，即當只選擇一個基數 a 並且我們只迭代一次時，錯誤機率最多為 1/4。我們正在測試 90,000 到 100,000 的奇數。

我已經用 Java 編寫了實現，並且隨著測試的執行，我看到很多 0.5 的機率。這使我相信我的實施存在問題。

我看到錯誤機率為 0.5 的一些奇數是：90007 91571 94343

還有更多（測試仍在執行）。

更新：這是我實現的算法

Miller–Rabin Primality Test
Input: prime candidate ˜ p with ˜ p−1 = 2ur and security parameter s
Output: statement “ ˜ p is composite” or “ ˜ p is likely prime”
Algorithm:
FORi = 1 TO s
   choose random a ∈ {2,3, . . . , ˜ p−2}
   z ≡ ar mod ˜ p
      IF z ≡ 1 and z ≡ ˜ p−1
         FOR j = 1 TO u−1
            z ≡ z2 mod ˜ p
            IF z = 1
               RETURN (“ ˜ p is composite”)
         IF z = ˜ p−1
            RETURN (“ ˜ p is composite”)
RETURN (“ ˜ p is likely prime”)

這是實現，如果有人可以查看並確定問題所在，我將不勝感激。

謝謝

public BigInteger mr(int x, int y){
   int u = 0;
   BigInteger p = BigInteger.valueOf(x);
   BigInteger r = p.subtract(ONE);
   BigInteger a = BigInteger.valueOf(y);

   while (r.mod(TWO).equals(ZERO)){
       u++;
       r = r.divide(TWO);
   }

   BigInteger z = a.modPow(r, p);
   if ((!z.equals(ONE) && !z.equals(p.subtract(ONE)))){
       int j = 1;
       for (; j < u; j++){
           z = z.modPow(TWO, p);
       }
   }
   return z;
}

public boolean isPrime(int n){
   if ( n % 2 == 0)
       return false;

   for (int i = 3; i <= Math.sqrt(n) + 1; i+=2){
       if (n % i == 0)
           return false;
   }
   return true;
}

public static void main(String[] args) {
   double ea;
   MillerRabin mr = new MillerRabin();
   int count = 0;
   BigInteger ans;
   for (int n = 90001; n< 100000; n+=2){
       count = 0;
       for (int a = 1; a < n; a++){
           ans = mr.mr(n, a);
           if (mr.isPrime(ans.intValue())){
               count++;    
           }

       }
       ea = ((double)count) / (n-1);
       System.out.println(ea);
   }
}

問題是你弄錯了算法。你用它來生成一個整數（它是 1 之一， $ x-1 $ ， 或者 $ y^{x-1} \bmod x $ ，然後如果該整數是素數，則說“素數”。

這是不正確的；實際上，您列出的三個整數 (90007 91571 94343) 都是素數，米勒拉賓在給定素數時應該總是返回素數。

相反，MR 的正確實現應該：

• 如果初始計算是 $ y^{(x-1)/2^u} $ 是 1 或 $ x-1 $ ，結論可能是素數。
• 做 $ u-1 $ 平方運算，如果其中任何一個的結果是 $ x-1 $ , 得出可能是素數, 如果是 1, 得出“複合”
• 如果，之後 $ u-1 $ 平方操作，你永遠不會打 $ x-1 $ ，總結“複合”

引用自：https://crypto.stackexchange.com/questions/30790