计算 pow(a,b) mod n

Question

我想计算 a 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;
}

原文由 Moein Hosseini 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

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

施奈尔，布鲁斯 (1996)。应用密码学：C 中的协议、算法和源代码，第二版（第二版）。威利。国际标准书号 978-0-471-11709-4。

---

请注意，在此简化版本中，乘法 result * base 和 base * base 会溢出。如果模数大于 T 宽度的一半（即超过最大值 T 值的平方根），则应使用合适的模乘算法代替 - 请参阅对 原始类型进行模乘法的方法的 答案。

原文由 Blastfurnace 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这是另一种方式。请记住，当我们在 mod m --- 下找到 modulo multiplicative inverse of a 时。然后

a 和 m 必须是 coprime 彼此。

我们可以使用 gcd extended 来计算 modulo multiplicative inverse 。

当 a 和 b 可以有超过 10 5位时计算 a b mod m ，那么计算结果就很棘手。

下面的代码将完成计算部分：

 #include <iostream>
#include <string>
using namespace std;
/*
*   May this code live long.
*/
long pow(string,string,long long);
long pow(long long ,long long ,long long);
int main() {
    string _num,_pow;
    long long _mod;
    cin>>_num>>_pow>>_mod;
    //cout<<_num<<" "<<_pow<<" "<<_mod<<endl;
    cout<<pow(_num,_pow,_mod)<<endl;
   return 0;
}
long pow(string n,string p,long long mod){
    long long num=0,_pow=0;
    for(char c: n){
        num=(num*10+c-48)%mod;
    }
    for(char c: p){
        _pow=(_pow*10+c-48)%(mod-1);
    }
    return pow(num,_pow,mod);
}
long pow(long long a,long long p,long long mod){
    long res=1;
    if(a==0)return 0;
    while(p>0){
        if((p&1)==0){
            p/=2;
            a=(a*a)%mod;
        }
        else{
            p--;
            res=(res*a)%mod;
        }
    }
    return res;
}

此代码有效，因为 a b mod m 可以写为 (a mod m) b mod m-1 mod m 。

希望它有帮助 { :)

原文由 devp 发布，翻译遵循 CC BY-SA 4.0 许可协议