RSA实现中幂函数返回负值的原因及大n值适配数据类型咨询

为什么会返回负值？ #

你遇到的负值问题，根源是有符号整数溢出。虽然long的最大值确实是9223372036854775807（约9.2e18），但在你的幂运算逻辑中，中间步骤的乘法可能会悄悄越过这个上限：

• 当n是9位数字（以9开头）时，x % n的结果可能接近999,999,999，它的平方是999999998000000001（约1e18），看起来没超过long的最大值，但如果指数y很大，经过多次平方迭代后，某次x*x的计算可能刚好触发有符号溢出——此时数值会直接绕回负数区间，后续的模运算也无法修正这个错误，最终返回负值。
• 更关键的是，你当前的写法是先完成乘法再取模，而不是在乘法过程中就控制数值范围，这就给溢出留下了可乘之机。

针对10-15位n的解决方案 #

当n扩展到10-15位时，x % n的结果会更大，直接相乘必然会超出long甚至Decimal/double的范围（double会丢失精度，Decimal虽精度高但运算效率低且仍有溢出风险）。最靠谱的选择是使用Java的BigInteger类，它专门用于处理任意大小的整数，并且内置了安全的模幂运算方法，完全不用手动处理溢出问题。

改进后的代码示例 #

方案1：直接使用BigInteger内置方法（推荐）

这是最简洁且安全的实现方式，适合实际开发：

import java.math.BigInteger;

private BigInteger power2(BigInteger x, BigInteger y, BigInteger n) {
    return x.modPow(y, n);
}

方案2：手动实现安全模幂（适合学习目的）

如果想自己实现逻辑，需要先写一个安全的模乘法，通过加法和位移模拟乘法，全程保持数值在模n的范围内：

private long safeModMultiply(long a, long b, long n) {
    long result = 0;
    a = a % n;
    while (b > 0) {
        if ((b & 1) == 1) {
            result = (result + a) % n;
        }
        a = (a * 2) % n;
        b >>= 1;
    }
    return result;
}

// 修改后的幂运算函数
private long power2(long x, long y, long n) {
    long temp = 1;
    x = x % n;
    while (y > 0) {
        if ((y & 1) == 1) {
            temp = safeModMultiply(temp, x, n);
        }
        x = safeModMultiply(x, x, n);
        y >>= 1;
    }
    return temp;
}

总结 #

• 负值问题的核心是中间乘法触发了long的有符号溢出，改用安全模乘法或直接用BigInteger就能彻底解决。
• 处理10-15位的大n时，BigInteger是最优选择，它既安全又省去了手动处理溢出的繁琐细节。

内容的提问来源于stack exchange，提问作者yajiv