561がFermatテストでtrueを返す

Question

このFermatのアルゴリズムを使って素数をテストした結果、Carmichael数（561など）で常に真を返すとは限りませんでした。私は問題を見つけようとしましたが、アルゴリズムに間違いはありません。何が問題なの？

import java.util.Scanner; 
import java.util.Random; 
import java.math.BigInteger; 

public class FermatTest { 

    private final static Random rand = new Random(); 

    private static BigInteger getRandomFermatBase(BigInteger n) 
    { 
     while (true) 
     { 
      final BigInteger a = new BigInteger (n.bitLength(), rand); 
      if (a.compareTo(BigInteger.ONE) == 1 && a.compareTo(n) < 0) 
      { 
       return a; // 1 <= a < n 
      } 
     } 
    } 

    public static String checkPrime(BigInteger n, int maxIterations) 
    { 
     if (n.equals(BigInteger.ONE)) 
      return "is composite"; 

     for (int i = 0; i < maxIterations; i++) 
     { 
      BigInteger a = getRandomFermatBase(n); //generate random a 
      a = a.modPow(n.subtract(BigInteger.ONE), n); //a^(p-1) mod p 

      if (!a.equals(BigInteger.ONE)) // not equals 1 
       return "is composite"; 
     } 
     return "is probably prime"; 
    } 

    public static void main(String[] args) 
    { 
     long start = System.nanoTime(); 
     BigInteger n = new BigInteger("561"); 
     System.out.println(n + " " + checkPrime(n , 20)); 
     float time = System.nanoTime() - start; 
     System.out.println("Time: " + (long) time + " nanoseconds"); 
     time = time/(1000000000); 
     System.out.println("Time: " + time + " seconds"); 
    } 
} 

Answer 1

あなた自身で問題を特定しました。すべての可能な塩基についてFermatテストによって不適切にプライムマークされているいくつかの数字、Carmichael数があります。それは数論の単なる事実です。プライムまたはコンポジットと区別するためには、別のテストが必要です。