c++ - 简化模块化幂运算C++

我正在尝试为RSA加密系统编写解密函数，对于很小的数字，一切似乎都可以正常工作，但是有时输出只是不正确（我认为原因可能是浮点错误或某种原因。堆栈溢出）。

导致我出现问题的过程可以简化为（11 ^ 23）mod 187，但如果有人希望看到它，我将提供完整的代码。我知道答案应该是88，因为这是西蒙·辛格（Simon Singh）博士在“密码本”附录J中使用的示例（我也使用Wolfram Alpha进行了检查）。但是，我得到的结果为149。但是，数字较小时，它与Wolfram Alpha一致。

我的想法是，我需要使用以下知识来简化模幂运算：

a ^ b = a ^ c * a ^ d [其中c + d = b]

但是，我仍然不确定100％是否是这个问题，这是我第一次出现堆栈溢出吗？ （我仍然不是100％知道那是什么意思）。在没有人问我之前，这不是什么功课，如果这个问题看起来很琐碎，我感到抱歉。如果所有人都认为这样做太难了，那么我愿意使用gmp.h，但是如果我完全诚实，我宁愿不使用。我的代码如下（上半部分是计算私钥，我认为这与我遇到的问题无关，但是为了防止我错了，我已经将其包含在内），我真的希望你们能提供帮助，谢谢你非常提前。

#include <iostream>
#include <math.h>

using namespace std;

unsigned int modinv(unsigned int u, unsigned int v)
{
    unsigned int inv, u1, u3, v1, v3, t1, t3, q;
    int iter;

    u1 = 1;
    u3 = u;
    v1 = 0;
    v3 = v;

    iter = 1;

    while (v3 != 0)
    {

        q = u3 / v3;
        t3 = u3 % v3;
        t1 = u1 + q * v1;

        u1 = v1; v1 = t1; u3 = v3; v3 = t3;
        iter = -iter;
    }

    if (u3 != 1)
        return 0;
    if (iter < 0)
        inv = v - u1;
    else
        inv = u1;
    return inv;
}

int main()
{ long unsigned int p = 17;
long unsigned int q = 11;
long unsigned int phi = (p-1)*(q-1);
long unsigned int e = 7;
long unsigned int c = 11;
long unsigned int n = p*q;
long unsigned int d = modinv (e,phi);
    {
         cout << fmod (pow (c, d), n);
    }
    return 0;
}

最佳答案

11 ^ 23约为2 ^ 80。只能将最大2 ^ 53的整数精确表示为双浮点数。因此fmod（pow（c，d），n））返回一个近似值。这不适用于密码学。

添加您可以使用重复平方进行模幂运算。查看Wikipedia上有关“平方求幂”的文章