计算pow(a,b)mod n

Question

我想计算一个用于RSA解密的^b mod n.我的代码(如下)返回错误的答案.这有什么问题？

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

Answer 1

您可以尝试这个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;
}

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

Schneier,Bruce(1996).应用密码学:C,第二版(第2版)中的协议,算法和源代码.威利.ISBN 978-0-471-11709-4.

请注意,乘法result * base和base * base在此简化版本中会出现溢出.如果模数大于宽度的一半T(即大于最大值的平方根T),那么应该使用合适的模乘法算法 - 参见对基本类型进行模乘的方法的答案.

Answer 2

为了计算pow(a,b) % n用于RSA解密,我遇到的最佳算法是Primality Testing ¹⁾,如下所示:

 int modulo(int a, int b, int n){
    long long x=1, y=a; 
    while (b > 0) {
        if (b%2 == 1) {
            x = (x*y) % n; // multiplying with base
        }
        y = (y*y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

有关详细信息,请参阅以下参考

¹⁾ Primality测试:非确定性算法 - topcoder

Answer 3

通常它是这样的:

while (b)
{
    if (b % 2) { res = (res * a) % n; }

    a = (a * a) % n;
    b /= 2;
}

return res;

Answer 4

我看到的唯一实际逻辑错误是这一行:

if (b % n == 1)

这应该是这样的:

if (b % 2 == 1)

但是你的整体设计是有问题的:你的函数执行O(b)乘法和模运算,但是你的使用b / 2并a * a暗示你的目标是执行O(log b)运算(通常是模幂运算的方式).