c ++中大数字的模乘

Question

我有三个整数A,B(小于10 ^ 12)和C(小于10 ^ 15).我想计算(A*B)%C.我知道

(A * B) % C = ((A % C) * (B % C)) % C

但是如果A = B = 10 ^ 11,那么上面的表达式将导致整数溢出.对于上述情况是否有任何简单的解决方案,或者我必须使用快速乘法算法.

如果我必须使用快速乘法算法,那么我应该使用哪种算法.

编辑:我在C++中尝试过上述问题(不会导致溢出,不确定原因),但答案应该是零吗？

提前致谢.

Answer 1

您可以使用Schrage的方法解决此问题.这允许您将两个有符号数相乘,a并且z两者都具有一定的模数,m而不会生成大于该数的中间数.

它基于模数的近似因子分解m,

m = aq + r 

即

q = [m / a]

和

r = m mod a

where []表示整数部分.如果r < q和0 < z < m ? 1,则两个a(z mod q)和r[z / q]横亘在范围0,...,m ? 1和

az mod m = a(z mod q) ? r[z / q]

如果这是否定的则添加m.

[该技术经常用于线性同余随机数发生器].

Answer 2

鉴于您的公式和以下变化:

(A + B) mod C = ((A mod C) + (B mod C)) mod C 

您可以使用分而治之的方法来开发既简单又快速的算法:

#include <iostream>

long bigMod(long  a, long  b, long c) {
    if (a == 0 || b == 0) {
        return 0;
    }
    if (a == 1) {
        return b;
    }
    if (b == 1) {
        return a;
    } 

    // Returns: (a * b/2) mod c
    long a2 = bigMod(a, b / 2, c);

    // Even factor
    if ((b & 1) == 0) {
        // [((a * b/2) mod c) + ((a * b/2) mod c)] mod c
        return (a2 + a2) % c;
    } else {
        // Odd exponent
        // [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c
        return ((a % c) + (a2 + a2)) % c;
    }
}

int main() { 
    // Use the min(a, b) as the second parameter
    // This prints: 27
    std::cout << bigMod(64545, 58971, 144) << std::endl;
    return 0;
}

这是 O(log N)