Using the mpz_powm functions from the GMP/MPIR libraries with negative exponents

Posted by Mihai Todor on Stack Overflow See other posts from Stack Overflow or by Mihai Todor
Published on 2012-06-24T21:03:18Z Indexed on 2012/06/24 21:16 UTC
Read the original article Hit count: 219

Filed under:
|
|
|
|

Please consider the following code:

mpz_t x, n, out;

mpz_init_set_ui(x, 2UL);
mpz_init_set_ui(n, 7UL);
mpz_init(out);

mpz_invert(out, x, n);
gmp_printf ("%Zd\n", out);//prints 4. 2 * 4 (mod 7) = 1. OK

mpz_powm_ui(out, x, -1UL, n);//prints 1. 2 * 1 (mod 7) = 2. How come?
gmp_printf ("%Zd\n", out);

mpz_clear(x);
mpz_clear(n);
mpz_clear(out);

I am unable to understand how the mpz_powm functions handle negative exponents, although, according to the documentation, it is supposed to support them. I would expect that raising a number to -1 modulo n is equivalent to inverting it modulo n. What am I missing here?

© Stack Overflow or respective owner

Related posts about c++

Related posts about primes