biginteger - 是否有一种节省空间的方法来计算高指数的 gcd？

Question

基本上，我正在编写一个程序，该程序可以处理溢出 cpp 整数的大整数值。我正在尝试计算如下内容: gdc(pow(a, b), c) 其中 a ^ b 是溢出整数限制的值。有没有一种方法可以做到这一点，而我不必依赖大整数库？如果没有，有推荐的大整数库吗？

Answer 1

我们可以使用 greatest common divisor 的属性 gcd(a, b) = gcd(a % b, b) 。因此 gcd(pow(a, b), c) = gcd(pow(a, b) % c, c) = gcd(powmod(a, b, c), c) ，其中 powmod() 是 modular exponentiation 。

在我的 C++ 代码中，下面的 PowMod() 是使用 exponentiation by squaring 方法实现的。

Try it online!

#include <cstdint>
#include <iostream>

using Word = uint32_t;
using DWord = uint64_t;

Word GCD(Word a, Word b) {
    Word t = 0;
    while (b != 0) {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

Word PowMod(Word a, Word b, Word c) {
    Word r = 1;
    while (b != 0) {
        if (b & 1)
            r = (DWord(r) * a) % c;
        a = (DWord(a) * a) % c;
        b >>= 1;
    }
    return r;
}

int main() {
    Word const
        a = 2645680092U, b = 3562429202U, c = 3045001828U,
        powmod = PowMod(a, b, c), gcd = GCD(powmod, c);
    std::cout << "a = " << a << ", b = " << b
        << ", c = " << c << std::endl;
    std::cout << "PowMod(a, b, c) = "
        << powmod << std::endl; // 592284924
    std::cout << "GCD(PowMod(a, b, c), c) = "
        << gcd << std::endl; // 1892
}

输出:

a = 2645680092, b = 3562429202, c = 3045001828
PowMod(a, b, c) = 592284924
GCD(PowMod(a, b, c), c) = 1892

给出了正确的结果，可以通过以下简单的Python程序来验证，给出相同的结果:

Try it online!

import random, math
random.seed(0)
bits = 32
while True:
    c = random.randrange(1 << (bits - 1), 1 << bits)
    a = random.randrange(1 << (bits - 1), 1 << bits) % c
    b = random.randrange(1 << (bits - 1), 1 << bits)
    pm = pow(a, b, c)
    gcd = math.gcd(pm, c)
    if gcd >= 1000:
        print('a =', a, ', b =', b, ', c =', c,
            ', powmod =', pm, ', gcd =', gcd)
        break

输出:

a = 2645680092 , b = 3562429202 , c = 3045001828 ,
    powmod = 592284924 , gcd = 1892

如果您有 GCC/CLang 编译器，则可以通过更改以下代码行将 Word 设为 64 位，将 DWord 设为 128 位:

using Word = uint64_t;
using DWord = unsigned __int128;

我的代码支持 32 位输入，但经过此更改，您可以拥有 64 位输入。

---

第 2 部分。使用大整数算术库 GMP 。

如果由于某种原因你有很大的输入整数，那么你可以使用很棒的库 GMP 进行大型算术运算(它支持整数、有理数、 float )。

该库包含所有 mathematical operations ，包括 modular exponentiation (PowMod) 和一些 number theoretical 函数(包括 GCD)。此外，这个库非常受欢迎并且经过高度优化。

在下面的代码中，我做了与上面的代码相同的事情，但仅使用 GMP 的函数。作为示例，我使用 512 位整数来表明它可以接受大输入(甚至可以接受数百万位数字):

Try it online!

#include <iostream>
#include <cstdlib>
#include <gmpxx.h>

int main() {
    mpz_class const
        a("1953143455988359840868749111326065201169739169335107410565117106311318704164104986194255770982854472823807334163384557922525376038346976291413843761504166", 10),
        b("5126002245539530470958611905297854592859344951467500786493685495603638740444446597426402800257519403404965463713689509774040138494219032682986554069941558", 10),
        c("4396071968291195248321035664209400217968667450140674696924686844534284953565382985421958604880273584922294910355449271193696338132720472184903935323837626", 10);
    
    mpz_class powmod, gcd;
    // PowMod
    mpz_powm(powmod.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t(), c.get_mpz_t()); // 1632164707041502536171492944083090257113212090861915134477312917063125646194834706890409016008321666479437224930114914370387958138698748075752168351835856
    // GCD
    mpz_gcd(gcd.get_mpz_t(), powmod.get_mpz_t(), c.get_mpz_t()); // 51842
    // Output
    std::cout << "PowMod = " << powmod.get_str() << std::endl
              << "GCD = " << gcd.get_str() << std::endl;
}

输出:

PowMod = 1632164707041502536171492944083090257113212090861915134477312917063125646194834706890409016008321666479437224930114914370387958138698748075752168351835856
GCD = 51842

要在Linux下使用GMP库，只需安装sudo apt install libgmp-dev并编译clang++ -std=c++11 -O2 -lgmp -o main main.cpp即可。

在 Windows 下使用 GMP 有点棘手。一种方法是自己构建 MPIR 库，它是 GMP 的 Windows 友好克隆。另一种方法是安装 MSYS 并使用我在其他答案中编写的 following these instructions 中预构建的 GMP。