论坛首页 › 通信 › 请教如何求“快速幂取模”的底数

zzh90513 发表于 2020-1-5 21:22:04

请教如何求“快速幂取模”的底数

如题，现在已知快速幂取模的算法，求“base”底数的算法如何推导，数学都忘光了。。。
int PowMod(int base, int pow, int n)
{
    int a = base, b = pow, c = 1;
   
    while ( b != 0)
    {
      while ((b & 1) == 0)
      {
            b >>= 1;
            a = (int)((long)(a * a) % n);
      }
      
      b--;
      c=(int) ((long)(a * c) % n);
    }
   
    return c;
}

canspider 发表于 2020-1-6 08:16:15

模幂运算是RSA算法的核心，数学上没有求底公式
目前的方法只有暴力搜索，不过你的底数也就32位，搜索起来也要不了多久

zzh90513 发表于 2020-1-6 08:58:01

canspider 发表于 2020-1-6 08:16
模幂运算是RSA算法的核心，数学上没有求底公式
目前的方法只有暴力搜索，不过你的底数也就32位，搜索起来也 ...

谢谢，不是反推底数，现在情况是，下位机传入“底数”，上位机PowMod的结果是真实数据，我现在知道pow和n的值；
我有真实数据，想对接上位机，如何能算出符合这个算法的“底数”呢？

canspider 发表于 2020-1-6 09:43:27

zzh90513 发表于 2020-1-6 08:58
谢谢，不是反推底数，现在情况是，下位机传入“底数”，上位机PowMod的结果是真实数据，我现在知道pow和n ...

按照目前已知的理论算不出来，只能穷举
你还可以反编译上位机软件，做一个补丁绕过这个检测机制

查看完整版本: 请教如何求“快速幂取模”的底数