计算 pow(a,b) mod n

I want to calculate a^b mod n for use in RSA decryption. My code (below) returns incorrect answers. What is wrong with it?

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;
}

您可以在第 10 页的文献中找到该算法和相关讨论。 244 的

布鲁斯·施奈尔 (1996)。应用密码学：C 语言协议、算法和源代码，第二版（第二版）。威利。 ISBN 978-0-471-11709-4。

注意乘法result * base and base * base在此简化版本中可能会发生溢出。如果模数大于宽度的一半T（即大于最大值的平方根T值），那么应该使用合适的模乘算法 - 请参阅答案使用原始类型进行模乘的方法 /q/12168348.