我发现这个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");
}
}
你自己发现了问题。有一些数字,即卡迈克尔数字,通过费马试验对所有可能的碱基进行了不恰当的标记。这只是数论的一个事实。您将需要一个不同的测试来区分数字作为素数或复合数。