计算 pow(a,b) mod n [英] Calculating pow(a,b) mod n

问题描述

我想计算 a^b mod n 以用于 RSA 解密.我的代码(如下)返回不正确的答案.有什么问题吗?

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 那里得到的.

You can try this C++ code. I've used it with 32 and 64-bit integers. I'm sure I got this from 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 的

You can find this algorithm and related discussion in the literature on p. 244 of

施奈尔，布鲁斯 (1996).应用密码学:C 语言中的协议、算法和源代码，第二版(第 2 版).威利.ISBN 978-0-471-11709-4.

Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.

<小时>

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

---

Note that the multiplications result * base and base * base are subject to overflow in this simplified version. If the modulus is more than half the width of T (i.e. more than the square root of the maximum T value), then one should use a suitable modular multiplication algorithm instead - see the answers to Ways to do modulo multiplication with primitive types.

这篇关于计算 pow(a,b) mod n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！