c++ - 使用 mpz_powm 计算功率模数

Question

我正在尝试使用 mpz_powm ( link ) 计算一个小数到一个大幂 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。最初，我认为我可能已经超过了 number 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 是模运算的预期结果。