Java BigInteger版快速幂函数错误排查及修正请求

你的BigInteger版快速幂代码存在两个关键问题：

1. 对象引用比较错误：判断y是否为奇数时，使用了(y.and(BigInteger.ONE)) != BigInteger.ZERO，这是错误的。BigInteger是引用类型，==/!=比较的是对象内存地址而非数值内容。即使两个BigInteger数值相同，它们的引用也可能不同，导致条件判断失效。
2. 缺少中间模运算：原int版本中由于int溢出会隐式截断，但BigInteger支持任意大整数，若不在每次乘法后取模，会导致中间结果过大，不仅降低效率，还可能和原逻辑的预期结果出现偏差（你的测试用例中主要问题是第一个，但添加中间模运算更规范）。

修正后的代码 #

static BigInteger power(BigInteger x, BigInteger y, BigInteger p) {
    BigInteger res = BigInteger.ONE; // 初始化结果
    x = x.mod(p); // 先将x模p，避免初始值过大

    while (y.compareTo(BigInteger.ZERO) > 0) {
        // 判断y是否为奇数，使用equals()比较数值
        if (y.and(BigInteger.ONE).equals(BigInteger.ONE)) {
            res = res.multiply(x).mod(p); // 乘法后立即模p
        }

        y = y.shiftRight(1); // y = y/2
        x = x.multiply(x).mod(p); // x平方后模p
    }
    return res;
}

测试验证 #

调用power(BigInteger.valueOf(2), BigInteger.valueOf(5), BigInteger.valueOf(13))，计算过程如下：

• 初始：res=1，x=2%13=2，y=5
• 第一次循环（y=5，奇数）：res=12%13=2；y=2；x=22%13=4
• 第二次循环（y=2，偶数）：res不变；y=1；x=4*4%13=16%13=3
• 第三次循环（y=1，奇数）：res=23%13=6；y=0；x=33%13=9
• 循环结束，返回6，与预期一致。

内容的提问来源于stack exchange，提问作者parsa.ni