英文:
What complexity does mpz_powm in GMP have?
问题
GMP函数mpz_powm的复杂度是多少？
有许多实现模指数运算的方法。它是否使用“从右到左的二进制方法”，其时间复杂度为O(log e)？
我想将其用于大指数，这对于O(e)不可扩展。
英文:
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).
答案1
得分: 0
我只是基于 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); // 只是为我调用 mpz_init/free()。
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);
}
}
}
英文:
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);
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论