计算pow（a，b）mod n

Z时代
2024-01-10
分类：问答

我想计算一个b mod n用于RSA解密。我的代码（如下）返回错误的答案。怎么了

unsigned long int decrypt2(int a,int b,int n)
{
    unsigned long int res = 1;
    for (int i = 0; i < (b / 2); i++)
    {
        res *= ((a * a) % n);
        res %= n;
    }
    if (b % n == 1)
        res *=a;
    res %=n;
    return res;
}

回答：

您可以尝试此C ++代码。我已将其与32位和64位整数一起使用。我确定我是从SO那里得到的。

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

您可以在p的文献中找到此算法和相关讨论。244之