相关疑难解决方法(0)

什么是Java 7中的方法的复杂性pow，并isProbablePrime在BigInteger上课吗？

我知道 Rabin 测试的简单实现是 O(k(log(n))^3) 复杂度，并且可以通过结合Schönhage-Strassen 算法来快速乘以长整数来降低复杂度。

嗨我想以最及时优化的方式乘以2大整数.我目前正在使用karatsuba算法.任何人都可以建议更优化的方式或算法来做到这一点.

谢谢

public static BigInteger karatsuba(BigInteger x, BigInteger y) {

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        System.out.println(N);
        if (N <= 2000) return x.multiply(y);                // optimize this parameter

        // number of bits divided by 2, rounded up
        N = (N / 2) + (N % 2);

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

        // compute …