fermat素性检验与carmichael数

xu3bshqb  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(256)

我在玩素数和费马的小定理。我读到卡迈克尔数,他们应该通过测试。问题是,当我测试它并使用两个不同的条件时,它应该以相同的结果结束,但事实并非如此。
代码:

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。应该是一样的,不是吗?我的代码有错误还是我误解了什么?

lawou6xi

lawou6xi1#

问题是当a=3时,您的注解条件返回false,这是因为3和561不是相对素数!卡迈克尔数要求gcd(a,n)=1(请参考维基百科:https://en.wikipedia.org/wiki/carmichael_number).
所以在你的程序中,你应该首先检查“a”和“n”是相对素数,然后再应用注解条件。

相关问题