计算 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

---

你尝试在调试器中逐步运行你的代码了吗？你能举个例子说明出错的地方在哪里吗？ - Oliver Charlesworth

为什么你不使用 pow(a,b) % n？ - Jeremy D

似乎你在最后的 if 语句中需要使用 % 2 而不是 % n。 - Lol4t0

对于这个例子，int 溢出了，但是 64 位类型已经足够了。然而，如果你真的要使用 RSA，你需要大整数，gmp 是一个选择（并且具有模幂）。 - Daniel Fischer

@JeremyD：因为（a）pow() 是一个浮点运算，而且（b）即使它不是，计算整个a^b只为了在取模运算时扔掉大部分结果也相当浪费。 - SamB

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

您可以在Schneier, Bruce（1996年）的著作《应用密码学：C语言协议，算法和源代码》第二版（第2版），p.244中找到此算法及相关讨论。

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

- Blastfurnace

---

+1（我本来就想留言的），这对这个问题非常有帮助。如果能找到原始来源那就太好了。 - Shafik Yaghmour

如果modulus > sqrt(std::numeric_limits<T>::max())怎么办？那种情况下，(result*base)可能会溢出，导致结果不正确。 - Ruud

为了避免这种情况，您可以使用您喜欢的模乘函数来替换那些乘法。例如：如何使用原始类型进行取模乘法的方法。 - Blastfurnace

为了使modpow(x, 0, 1)正常工作，将T result = 1;更改为T result = modulus > 1;或result = 1%modulus。 - chux - Reinstate Monica

这段代码如何避免在计算result * base和base * base时溢出T的范围？ - Toby Speight

Answer 2

为了计算用于RSA解密的 pow(a, b) % n ，我找到了最好的算法素性测试 ¹⁾，其步骤如下：

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

更多细节请参见以下参考资料。

---

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

- Shubham Khatri

---

你似乎假设long long比int有更宽的范围。但在C或C++中并没有这样的保证，所以这段代码仍然容易溢出。 - Toby Speight

Answer 3

通常是这样的：

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

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

return res;

- Kerrek SB

Answer 4

我看到唯一的实际逻辑错误是这一行代码：

if (b % n == 1)

应该是这个样子：

if (b % 2 == 1)

但是你的整体设计存在问题：你的函数执行了O(b)次乘法和模运算，但是你使用 b / 2 和 a * a 的方式表明你想要执行 O(log b) 次操作（这通常是模幂运算的做法）。

- ruakh

---

我认为另一个逻辑错误是：如果 a == 0，结果应该是 0 而不是 1。并且 a 应该被赋值给一个临时的64位变量，然后再用于乘法运算 - 以避免溢出。 - Christian Ammer

@ChristianAmmer：关于 a == 0 的问题。实际上不是这样的，因为只要 b > 0，res 就会至少乘以 a 或 a * a 一次。（如果 b == 0，那么即使 a == 0，1 也是一个完全有效的返回值。）关于将 a 分配给临时的 64 位变量：我想是这样的。其他评论者已经指出，32 位整数不足以用于实际的 RSA 加密，因此我的答案假定该函数仅用于尝试使用小数字并掌握其工作原理。也许我应该明确说明一下？ - ruakh

Answer 5

进行原始计算操作非常昂贵，因此您可以应用以下逻辑来简化解密过程。

从这里开始，

现在假设我们想要加密消息m=7，c=m^e mod n = 7^3 mod 33 = 343 mod 33 = 13。因此密文c=13。 为了检查解密，我们计算出m'=c^d mod n = 13^7 mod 33 = 7。注意，我们不必在这里计算13的7次方的完整值。我们可以利用以下事实：a = bc mod n = (b mod n).(c mod n) mod n，因此我们可以将一个潜在的大数分解成其组件，并结合更容易、更小的计算结果来计算最终值。 计算m'的一种方法如下：请注意，任何数字都可以表示为2的幂次和。因此，首先通过反复平方连续的值对33取模来计算13^2、13^4、13^8等的值。13^2 = 169 ≡ 4，13^4 = 4.4 = 16，13^8 = 16.16 = 256 ≡ 25。然后，由于7 = 4 + 2 + 1，我们有m' = 13^7 = 13^(4+2+1) = 13^4.13^2.13^1 ≡ 16 x 4 x 13 = 832 ≡ 7 mod 33。

- bragboy

---

好的，那似乎是他试图实现的算法。问题是他做错了什么。 - Dave Costa

Answer 6

你想计算 (a^b)%n 还是 a^(b%n)？

如果你想计算第一个，那么你的代码只在 b 为偶数时才有效，因为有 b/2。 "if b%n==1" 是错误的，因为这里不关心 b%n，而是关心 b%2。

如果你想计算第二个，那么循环是错误的，因为你循环了 b/2 次，而不是 (b%n)/2 次。

无论哪种情况，你的函数都是不必要复杂的。为什么要循环到 b/2 并尝试每次乘以 2 个 a？为什么不直接循环到 b 并每次乘以一个 a 呢？这将消除许多不必要的复杂性，从而消除潜在的错误。你是否认为通过减少循环次数，可以使程序更快？坦白说，这是一个糟糕的编程实践：微观优化。这并没有真正帮助太多：你仍然相同次数地乘以 a，你只是减少了测试循环的次数。如果 b 通常很小（例如一两位数），那么这并不值得。如果 b 很大，比如可能是百万级别，那么这是不够的，你需要更彻底的优化。

此外，为什么每次循环都要进行 %n？为什么不在最后只进行一次呢？

- Jay

---

在结尾处执行模数运算 --> res 会变得不必要地大并溢出（无论在他的示例中如何）。循环直到 b/2 --> 只有一半的迭代是必要的，因为编译器会优化并预计算 (a*a) % n。 - Christian Ammer

Answer 7

Calculating pow(a,b) mod n

1. A key problem with OP's code is a * a. This is int overflow (undefined behavior) when a is large enough. The type of res is irrelevant in the multiplication of a * a.

   The solution is to ensure either:

   • the multiplication is done with 2x wide math or
   • with modulus n, n*n <= type_MAX + 1

2. There is no reason to return a wider type than the type of the modulus as the result is always represent by that type.

   // unsigned long int decrypt2(int a,int b,int n)
   int decrypt2(int a,int b,int n)
   

3. Using unsigned math is certainly more suitable for OP's RSA goals.

---

请参见无需范围限制的模幂运算

。

// (a^b)%n
// n != 0

// Test if unsigned long long at least 2x values bits as unsigned
#if ULLONG_MAX/UINT_MAX  - 1 > UINT_MAX
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  unsigned long long result = 1u % n;  // Insure result < n, even when n==1
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (1ULL * a * a) %n;
    b >>= 1;
  }
  return (unsigned) result;
}

#else
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  // Detect if  UINT_MAX + 1 < n*n
  if (UINT_MAX/n < n-1) {
    return TBD_code_with_wider_math(a,b,n);
  }
  a %= n;
  unsigned result = 1u % n;
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (a * a) % n;
    b >>= 1;
  }
  return result;
}

#endif

- chux - Reinstate Monica

---

目前这是唯一一个确定问题原因并提出适当解决方案的答案。其他的回答都有可能溢出。 - Toby Speight

Answer 8

int类型通常不足以支持RSA（除非你处理的是小型简化示例）

你需要一个能够存储整数高达2²⁵⁶（用于256位RSA密钥）或2⁵¹²（用于512位密钥等）的数据类型。

- zed_0xff

Answer 9

这里有另一种方法。记住，当我们在模 m 下找到 a 的 模乘法逆元 时。

a 和 m 必须互质。

我们可以使用 gcd 扩展算法 来计算 模乘法逆元。

当 a 和 b 可以有超过 10⁵ 位数时，计算 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。

希望它有帮助 { :)

- Udesh

Answer 10

这（加密）更多是算法设计问题，而不是编程问题。重要的缺失部分是对现代代数的熟悉。我建议您在群论和数论中寻找巨大的优化。
如果n是一个质数，则pow(a,n-1)%n==1（假设无限位整数）。因此，基本上您需要计算pow(a,b%(n-1))%n；根据群论，您可以找到e，使得每个其他数字都等价于模n的e的幂。因此，范围[1..n-1]可以表示为e的幂的排列。给定找到n和以e为底数的a的对数的算法，计算可以显着简化。密码学需要大量的数学背景；如果没有足够的背景，我宁愿离开那个领域。

- Red.Wave