c++ - GMP-无模功率

Question

我正在尝试将任意大的数字提高到任意大的幂。据我所知，GMP 有一个函数可以执行此操作，但对结果应用模，还有一个函数可以让我将任意数字提高到 unsigned int 指数。有解决办法吗？

Answer 1

and a function that lets me raise an arbitrary number to an unsigned int exponent

它是一个 unsigned long int 指数，所以如果你在一个 unsigned long 是 64 位(或更多)的系统上，这将使你超出可用内存 future 几年(2^(2^64-1) 需要几个 EB 存储空间)。

如果您使用的是 32 位 unsigned long 系统，您可以将指数分成两部分，

if (exponent >= (1u << 31)) {
    mpz_pow_ui(base, base, exponent >> 31);
    mpz_pow_ui(base, base, 1u << 31);
}
mpz_pow_ui(base, base, exponent & ((1u << 31) - 1));

这很有可能需要比您拥有的更多的内存。

另一个问题是 GMP 使用 int 来计算肢体数量，因此通常您不能使用超过 (2^31 - 1)*BITS_PER_LIMB 位(BITS_PER_LIMB 通常是 32 位或 64 位，具体取决于平台)。

如果您认为您需要 a^b，其中 a > 1 和 b 不适合 unsigned long ( long)，无论如何你都会遇到 GMP 和你的内存问题。