BigIntegers对BigIntegers的力量

Question

我正在尝试使用BigInteger类在Java中实现Fermat,Miller-Rabin或AKS算法.

我认为我已经实现了Fermat测试,只是BigInteger类不允许将BigIntegers带入BigIntegers的强大功能(人们只能将BigIntegers带入原始int的强大功能).有没有解决的办法？

有问题的行在我的代码中表示:

public static boolean fermatPrimalityTest(BigInteger n)
{
    BigInteger a;
    Random rand = new Random();
    int maxIterations = 100000;

    for (int i = 0; i < maxIterations; i++) {
        a = new BigInteger(2048, rand);

        // PROBLEM WITH a.pow(n) BECAUSE n IS NOT A BigInteger
        boolean test = ((a.pow(n)).minus(BigInteger.ONE)).equals((BigInteger.ONE).mod(n));

        if (!test)
            return false;
    }

    return true;
}

Answer 1

我想BigInteger.modPow可能就是你要找的东西.注意费马测试中的"mod m".