我想计算一个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之
Schneier，Bruce（1996）。《应用密码学：C中的协议，算法和源代码》，第二版（第二版）。威利。ISBN 978-0-471-11709-4。
请注意，在此简化版本中，乘法result * base和base * base会溢出。如果模量大于宽度的一半T（即大于最大值的平方根T），则应该使用一种合适的模块化乘法算法-请参见 使用原始类型进行模乘法的方法 的答案。
result * base
base * base
T
