计算pow（a，b）mod n

计算pow（a，b）mod n

您可以尝试此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之

Schneier，Bruce（1996）。《应用密码学：C中的协议，算法和源代码》，第二版（第二版）。威利。ISBN
978-0-471-11709-4。

---

请注意，在此简化版本中，乘法

result * base

和

base *base

会溢出。如果模量大于宽度的一半

T

（即大于最大值的平方根

T

），则应该使用一种合适的模块化乘法算法-请参见
使用原始类型进行模乘法的方法 的答案。