BigIntegers对BigIntegers的力量 [英] BigIntegers to the power of BigIntegers

问题描述

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

I am trying to implement either the Fermat, Miller-Rabin, or AKS algorithm in Java using the BigInteger class.

我想我有实施费马测试，但BigInteger类不允许将BigIntegers带入BigIntegers的强大功能（只能使用BigIntegers）将BigIntegers带入原始内容的力量）。 有解决方法吗？

I think I have the Fermat test implemented except that the BigInteger class doesn't allow taking BigIntegers to the power of BigIntegers (one can only take BigIntegers to the power of primitive ints). Is there a way around this?

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

The problematic line is denoted in my code:

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;
}

推荐答案

我认为 BigInteger.modPow 可能就是您要找的东西。请注意费马测试中的mod m。

I think BigInteger.modPow might be what you're looking for. Note the "mod m" in Fermat's test.

这篇关于BigIntegers对BigIntegers的力量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！