Is there a c++ gmp library function that does the same as the python gmpy2 library divm(...) function?

Question

Just as the title says I am trying to find a function in the C++ gmp library that does the same thing as the gmpy2 python library's divm(...) function.

I can't imagine that gmpy2 has this method and the gmp C++ library has nothing that can do this same calculation.

If this does not exist, I'd appreciate any advice on making the divm function from scratch (still must be using gmp as I'm working with values larger than standard integers via mpz_class).

Thanks!

Answer 1

The C source code for that function can be found here, in GMPy_MPZ_Function_Divm. As you can see, it's not really a one-to-one mapping to the underlying C code but, when you strip away all the Python reference counting stuff, it looks pretty basic:

// numz, denz, and modz are copies of the arguments.
// resz, gcdz ar temporaries.

if (mpz_invert(resz, denz, modz)) {    // inverse exists?
    ok = 1;
} else {                               // num, den AND mod have a gcd > 1?
    mpz_init(gcdz);
    mpz_gcd(gcdz, numz, denz);
    mpz_gcd(gcdz, gcdz, modz);
    mpz_divexact(numz, numz, gcdz);
    mpz_divexact(denz, denz, gcdz);
    mpz_divexact(modz, modz, gcdz);
    mpz_clear(gcdz);
    ok = mpz_invert(resz, denz, modz);
}
if (ok) {
    mpz_mul(resz, resz, numz);
    mpz_mod(resz, resz, modz);
    mpz_clear(numz);
    mpz_clear(denz);
    mpz_clear(modz);
    return resz;
} else {
    mpz_clear(numz);
    mpz_clear(denz);
    mpz_clear(modz);
    return NULL;
}

---

Mathematically, it just calculates the expression b-1 * a % m for divm(a, b, m), assuming of course that that expression is valid (eg, b is non-zero).