C 中大数模 m 的幂

Question

我正在使用以下函数计算大数的模 m 的幂，其中 m 是任何整数，即(a^b)%m

long long power(long long x, long long y, long long p)
{
    long long res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

但是，对于某些号码，即使此功能也不起作用。例如，如果我调用

 power(1000000000000,9897,52718071807);

我得到一个负数作为输出。它的发生是由于以下原因：幂函数中有一行：

  x = (x*x) % p;

当x很大时，比方说x=46175307575，执行x=(x * x)%p后存储在x中的值变为负数。我不明白为什么会这样。即使 (x * x) 的值越过 long long int 的上限，我也没有将其值存储在任何地方，我只是存储 (x*x)%p 其值应介于 0 到 p 之间。另外，既然 p 没有跨越 long long 范围，那么 x 如何跨越它呢？请告诉我为什么会出现这个问题以及如何解决这个问题。

Answer 1

在GeeksForGeeks处是这个函数：

// Returns (a * b) % mod
long long moduloMultiplication(long long a,
                               long long b,
                               long long mod)
{
    long long res = 0;  // Initialize result

    // Update a if it is more than
    // or equal to mod
    a %= mod;

    while (b)
    {
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;

        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;

        b >>= 1;  // b = b / 2
    }

    return res;
}

用它代替

x = (x*x) % p;

即

x = moduloMultiplication(x, x, p);

而不是

res = (res*x) % p

即

res = moduloMultiplication(res, x, p);

Answer 2

如果Mod == (2^63-1) 那么这个解决方案将不起作用。

解：Mod <= 2^62

(p-1)*(p-1) > 2^63。所以会有溢出。你需要用模来实现乘法。

试试这个：

long long multiply(long long a,long long b,long long m){
if(b == 0){
    return 0;
}
if(b==1){
    return a%m;
}
if(b&1){
    return ((a%m)+multiply(a,b-1,m))%m;
}
long long x = multiply(a,b>>1,m);
return multiply(x,2,m);
}

long long bigmod(long long a,long long b, long long m){
if(b == 0){
    return 1;
}
if(b == 1){
    return a%m;
}
if(b & 1){
    return multiply(a%m,bigmod(a,b-1,m),m);
}
long long x = bigmod(a,b>>1,m);
return multiply(x,x,m);
}

Answer 3

除了@Doug Currie 提到的解决方案，您还可以使用 128 位数据类型__int128。

long long pow(long long a, long long b, long long mod)
{
    __int128 res = 1;
    while(b > 0)
    {
        if(b&1)
        {
            res = (res*a);
            res = res%mod;
        }
        b = b>>1;
        a = ((__int128)a*a)%mod;
    }
    return res;
}

Answer 4

欢迎使用有符号整数溢出和未定义行为 (UB)。

I am just storing (x*x)%p whose value should lie between 0 to p.

这是不正确的。 x*x 可能溢出 long long 数学，结果是 UB。。示例 UB 包含一个负数且操作数为正数的乘积..

some_negative_value % some_positive_p 导致负值。 - see ref。这超出了范围 [0...p).

解决方案是不要溢出有符号整数数学。

简单的第一步是使用无符号整数数学。

没有溢出问题的全方位解决方案在这里Modular exponentiation without range restriction

注意 OP 的代码也未能通过极端情况：power(some_x, 0, 1) 因为它 returns 1，而预期为 0。

// Fix
// long long res = 1;
long long res = 1%p;
// or 
long long res = p != 1;

C 中大数模 m 的幂

Power for big numbers modulo m in C

c

algorithm

function

long-long