What complexity does mpz_powm in GMP have?

Question

What complexity does the GMP function mpz_powm have?

There are many ways to implement modular exponentiation. Does it use "Right-to-left binary method" which runs in O(log e)?

I would like to use it for large exponents, which doesn't scale for O(e).

Answer 1

I just implemented my own based on another implementation in github. It's a simple implementation with similar run-time and which I also know is O(log e), and allowing me to log and stop where it freezes. This confirms the official implementation is as fast as I hoped, which sadly turned out to be not fast enough for my purposes.

#include <gmp.h>

// https://github.com/csknk/fast-modular-exponentiation/blob/master/cpp/main.cpp
void mod_exp_fast(mpz_t result, const mpz_t& b_in, const mpz_t& e_in, const mpz_t& m) {
    mpz_t b, e;
    MpzRaii(b, e); // Just calling mpz_init/free() for me.
    mpz_set(b, b_in);
    mpz_set(e, e_in);

    if (mpz_odd_p(e) != 0) {
        mpz_set(result, b);
    } else {
        mpz_set_ui(result, 1);
    }

    while (mpz_cmp_ui(e, 0) > 0) {
        // gmp_printf("mod_exp e=%d\n", mpz_sizeinbase(e, 2));
        mpz_powm_ui(b, b, 2, m);
        mpz_fdiv_q_2exp(e, e, 1);
        if (mpz_odd_p(e) != 0) {
            mpz_mul(result, result, b);
            mpz_mod(result, result, m);
        }
    }
}