CODEWITHSUNDEEP
c++gmp
nullgraph
nullgraph

Reputation: 307

Calculating power mod with mpz_powm

I'm trying to use mpz_powm (link) to calculate a small number to a big power mod a big number. Here is the code:

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

This gives me foo=0. Initially, I thought that I might have gone over some limit with the size of the number mod, and since 2^130=1.3611295e+39, I changed mod to:

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

this produces foo=1512713438470702986642486608412251521024. I'm not sure if this is correct either. What's going on here?

Upvotes: 1

Views: 2762

Answers (1)

user268396
user268396

Reputation: 11976

The first case is definitely correct since, 4^255 = (2^2)^255 = 2^510 = (2^130) * (2^380). So 0 is the expected outcome of the modulo operation.

Upvotes: 2

Related Questions