561이 Fermat 테스트에서 true를 반환합니다

Question

Fermat의 소수 테스트 알고리즘을 발견했는데 Carmichael 수 (예 : 561)가 항상 true가 아닌 것으로 나타났습니다. 문제를 찾으려고했지만 알고리즘에 문제가없는 것을 발견 할 수 없습니다. 무엇이 문제 일 수 있습니까?

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) 테스트에서 가능한 모든 염기를 부적절하게 표시 한 숫자 인 카 마이클 숫자가 있습니다. 그것은 숫자 이론에 불과합니다. 숫자를 소수 나 복합으로 차별화하려면 다른 테스트가 필요합니다.