Using the mpz_powm functions from the GMP/MPIR libraries with negative exponents
-
16-06-2021 - |
Question
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, -1, 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?
Solution 2
The problem is caused by the way in which the mpz_powm_ui function is declared:
void mpz_powm_ui (mpz t rop, mpz t base, unsigned long int exp, mpz t mod)
Perhaps this is a documentation bug, since exp will always be positive.
OTHER TIPS
Try to make -1 a signed number. In other words, don't use the unsigned interface, but make a real bignum with value -1.
To wit:
#include <gmpxx.h>
#include <iostream>
int main()
{
mpz_class n(7), k(2), res;
mpz_powm(res.get_mpz_t(), k.get_mpz_t(), mpz_class(-1).get_mpz_t(), n.get_mpz_t());
std::cout << res << std::endl;
}
Prints:
4
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow