CODEWITHSUNDEEP
cgmpmoduloexp
superstack
superstack

Reputation: 101

Use GNU MPZ library for modular exponentation

I never use GNU MPZ library before. I want to use it to calculate modular exponentiation of big inputs(result cannot stored in 8 bytes). So try to use gmp.h. but don't know how to switch between uint64_t to mpz_t type and convert result back to uint64_t . I try to use some builtin functions of gmp but return error segmentation fault: Code: 

#include <stdio.h>
#include <stdint.h>
#include <gmp.h>    
void mpz_set_ull( mpz_t rop, uint64_t op ){
   mpz_import(rop, 1, 1, sizeof(op), 0, 0, &op);
   }
int powmod(mpz_t result, mpz_t a,  mpz_t e,  mpz_t n) {
   // Use result as accum (temp variable)
  if (mpz_cmp_si(e,0) == 0) { // If exponent is zero
    mpz_set_ui(result, 1); // Set result to 1
    return 1;
  };
 mpz_set(result, a); // Set value of accum to a
 int bitptr = mpz_sizeinbase(e,2) - 1; // Find top bit in exponent
 for(bitptr--; bitptr >= 0; bitptr--) {
   mpz_mul(result,result,result); // result <-- result^2
   mpz_fdiv_r(result,result,n);   // result <-- result (mod n)
   if(mpz_tstbit(e,bitptr)) { // Is bit e[bitptr] == 1?
     mpz_mul(result,result,a);      // result <-- result*a
     mpz_fdiv_r(result,result,n);   // result <-- result (mod n)
    };
  };
return 1;
}
int main() {
  mpz_t mpz_g;
  mpz_t mpz_l;
  mpz_t mpz_p;
  mpz_t mpz_r;
  uint64_t r;       
  uint64_t p=1217409241131113809; //g^lm mod p
  uint64_t g=1103362698; 
  uint64_t lm = 137911680;
  mpz_set_ull( mpz_g, g );
  mpz_set_ull( mpz_l, lm );
  mpz_set_ull( mpz_p, p );
  powmod(mpz_r,mpz_g,mpz_l,mpz_p );
  r= mpz_get_ui (mpz_r);
  printf("---> %ld\n",r);
return 0;
}

Error: Segmentation fault (core dumped)

Upvotes: 1

Views: 332

Answers (1)

f9c69e9781fa194211448473495534
f9c69e9781fa194211448473495534

Reputation: 4620

Using GDB on your program, we can see the segmentation fault occurs in mpz_set_ull:

$ gcc -g -lgmp test.c 
$ gdb ./a.out 
(gdb) run
Starting program: ./a.out 

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7f12789 in __gmpz_import () from /usr/lib/libgmp.so.10
(gdb) bt
#0  0x00007ffff7f12789 in __gmpz_import () from /usr/lib/libgmp.so.10
#1  0x0000555555555209 in mpz_set_ull (rop=0x7fffffffe5e0, op=1103362698) at test.c:5
#2  0x0000555555555357 in main () at test.c:34

This is because the mpz_t you pass to mpz_import has not been initialized yet. GMP expects you to call mpz_init on the mpz_t before calling mpz_import.

You can fix this by inserting the following code in your main before you call mpz_set_ull:

  mpz_init(mpz_g);
  mpz_init(mpz_l);
  mpz_init(mpz_p);
  mpz_init(mpz_r);

Depending on how you use this code, you might also want to call mpz_clear on those variables when you are done with the computation.

Running your program with this modification gives me:

$ ./a.out 
---> 152166603192600961

This is the correct result for the example input you gave.

Upvotes: 1

Related Questions