快速幂模方法计算错误排查：5^20 mod7结果应为4却输出3

API 探路者

2026-8-19

快速幂模方法错误排查：5^20 mod7结果异常问题

你的快速幂模方法计算5^20 mod7时返回3，但正确结果应为4，核心错误是二进制位的遍历顺序搞反了。

错误原因分析

Integer.toString(x, 2)返回的是高位在前的二进制字符串，比如20的二进制是10100。你的代码从字符串的起始位置（最高位）开始遍历，而快速幂的正确逻辑需要从二进制的最低位开始遍历——因为每一位对应的是当前基数s的幂次（最低位对应2^{0，依次是2}1、2^2...），顺序颠倒会导致每一步的s对应的幂次完全错误，最终计算结果偏差。

修正后的代码

只需要调整循环的遍历方向，从二进制字符串的末尾（最低位）开始向前遍历：

public class cryptoLab1 {
    //y = a^x mod p
    public static BigInteger Mod(BigInteger a, int x, int p) throws Exception {
        if(x == 0) {
            return BigInteger.valueOf(1);
        }
        if(p == 0) {
            throw new Exception("P cannot be 0");
        }

        var t = Integer.toString(x, 2);
        var result = BigInteger.valueOf(1);
        var s = a;

        // 从二进制最低位（字符串末尾）开始遍历
        for (int i = t.length() - 1; i >= 0; i--) {
            if(t.charAt(i) == '1') {
                result = (result.multiply(s)).mod(BigInteger.valueOf(p));
            }
            s = (s.multiply(s)).mod(BigInteger.valueOf(p));
        }

        return result;
    }
}