我在玩素数和费马的小定理。我读到卡迈克尔数,他们应该通过测试。问题是,当我测试它并使用两个不同的条件时,它应该以相同的结果结束,但事实并非如此。
代码:
import java.math.BigInteger;
public class FermatTest {
public static boolean passesAllFermatTests(BigInteger n) {
BigInteger testValue = BigInteger.ONE;
while (testValue.compareTo(n) == -1) {
if (!passesFermatTest(n, testValue)) {
return false;
}
testValue = testValue.add(BigInteger.ONE);
}
return true;
}
public static boolean passesFermatTest(BigInteger n, BigInteger a) {
//if( !a.modPow(n.subtract(BigInteger.ONE), n).equals(BigInteger.ONE)) {
if(! a.modPow(n, n).equals(a)) {
return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(passesAllFermatTests(BigInteger.valueOf((long) 561)));
}
}
当我用这个条件运行它时,它返回true(pass it)。如果我用注解的条件运行它,它将返回false。应该是一样的,不是吗?我的代码有错误还是我误解了什么?
1条答案
按热度按时间lawou6xi1#
问题是当a=3时,您的注解条件返回false,这是因为3和561不是相对素数!卡迈克尔数要求gcd(a,n)=1(请参考维基百科:https://en.wikipedia.org/wiki/carmichael_number).
所以在你的程序中,你应该首先检查“a”和“n”是相对素数,然后再应用注解条件。