C#中Math.Pow计算RSA解密结果不符的问题排查咨询

嘿，这个问题我太熟了——本质上是浮点数精度不足在搞鬼！

你用Math.Pow(11, 23)计算大整数幂的时候，返回的是double类型的浮点数。而11^23的精确值是一个23位的整数（12164510040883203121），但double类型只能保证15-17位的有效数字，超过这个范围的数字会被近似存储，导致最终取模187的结果完全偏离预期。

1. 先验证理论正确性
   先手动用数论方法确认解密结果确实应该是88：

   • 因为187 = 17 × 11，根据中国剩余定理拆分计算：
     • 11^23 mod 11 = 0（任何11的倍数模11都是0）
     • 对模17，用费马小定理简化：11^16 ≡ 1 mod 17，所以11^23 = 11^(16+7) = 11^7 mod 17，计算得11^7 ≡ 3 mod 17
     • 找同时满足x ≡ 0 mod11且x≡3 mod17的数，最终得到x=88 mod187，说明理论结果是对的，问题出在代码的计算方式上。

2. 检查Math.Pow的实际输出
   在C#里打印Math.Pow(11,23)，你会发现它返回的是近似值（比如1.2164510040883202E+22），和精确整数存在误差——这就是取模结果错误的直接原因。

有两种可靠的方式避免这个问题：

方式一：手动实现快速幂模运算 #

不需要计算完整的大整数，每次运算都取模，保证数值始终在小范围内：

static long ModPow(long a, long exponent, long mod)
{
    long result = 1;
    a = a % mod; // 先将底数限制在模范围内
    while (exponent > 0)
    {
        // 指数为奇数时，将当前底数乘入结果
        if (exponent % 2 == 1)
        {
            result = (result * a) % mod;
        }
        // 指数折半，底数平方后取模
        exponent = exponent >> 1;
        a = (a * a) % mod;
    }
    return result;
}

// 调用示例
long decrypt = ModPow(11, 23, 187); // 结果为88，正确

方式二：使用BigInteger类（推荐） #

.NET的System.Numerics命名空间下的BigInteger支持任意精度的整数运算，自带的ModPow方法可以直接解决这个问题：

using System.Numerics;

// 加密
BigInteger encrypted = BigInteger.ModPow(88, 7, 187); // 输出11
// 解密
BigInteger decrypted = BigInteger.ModPow(11, 23, 187); // 输出88，正确

永远不要用浮点数函数（比如Math.Pow）来处理大整数的幂模运算——浮点数的精度限制会让结果完全不可靠。要么自己实现快速幂模，要么用专门的大整数类来保证运算精确性。

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