GMP中的mpz_powm有什么复杂性？

Question

GMP功能

mpz_powm

有多复杂？

有很多方法可以实现模幂。它是否使用“从右到左的二进制方法”，运行时间为 O(log e)？

我想将它用于大指数，但它不能缩放 O(e)。

Answer 1

我刚刚根据 github 中的另一个实现实现了自己的。这是一个简单的实现，具有类似的运行时间，我也知道它是 O(log e)，并允许我记录并在冻结的地方停止。这证实了官方的实施速度正如我所希望的那样快，但遗憾的是，这对于我的目的来说还不够快。

#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);
        }
    }
}