c++ - 使用 mpz_powm 计算功率 mod

Question

我正在尝试使用 mpz_powm （链接）来计算一个小数字到一个大功率 mod 一个大数字。这是代码：

#include <gmpxx.h>
#include <iostream>
using namespace std;

int main()
{
    mpz_class mod;
    mpz_pow_ui(mod.get_mpz_t(),mpz_class(2).get_mpz_t(),130);
    cout<<"mod="<<mod<<endl;
    mpz_class exp(255);
    mpz_class base(4);
    mpz_class foo;
    mpz_powm(foo.get_mpz_t(),base.get_mpz_t(),exp.get_mpz_t(),mod.get_mpz_t());
    cout<<"foo="<<foo<<endl;
}

这给了我 foo=0。最初，我认为我可能已经超出了数字 mod 的大小的一些限制，并且由于 2^130=1.3611295e+39，我将 mod 更改为：

mpz_pow_ui(mod.get_mpz_t(),mpz_class(10).get_mpz_t(),40);

这会产生 foo=1512713438470702986642486608412251521024。我也不确定这是否正确。这里发生了什么？

Answer 1

第一种情况肯定是正确的，因为4^255 = (2^2)^255 = 2^510 = (2^130) * (2^380). 0模运算的预期结果也是如此。