有没有 space 有效的方法来计算高指数的 gcd？

Question

基本上，我正在编写一个程序，该程序处理溢出 cpp 整数的大整数值。我正在尝试计算如下内容： gdc(pow(a, b), c) 其中 a ^ b 是超出整数限制的值。有没有办法在我不必依赖大型整数库的情况下执行此操作？如果没有，有没有推荐的大整数库？

Answer 1

我们可以使用 greatest common divisor that gcd(a, b) = gcd(a % b, b). Hence gcd(pow(a, b), c) = gcd(pow(a, b) % c, c) = gcd(powmod(a, b, c), c), where powmod() is 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 进行大型算术运算（它支持整数、有理数、浮点数）。

该库具有所有 mathematical operations, including modular exponentiation (PowMod) and some 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 library which is a Windows friendly clone of GMP. Another way is to install MSYS and use prebuilt GMP from there 我在另一个答案中写的。

有没有 space 有效的方法来计算高指数的 gcd？

Is there a space efficient way to compute the gcd of high exponents?

biginteger

integer-overflow

exponentiation