当除数大于两个大因子时的模积

Question

在我的C ++代码中，我有三个uint64_t变量：

uint64_t a =  7940678747;
uint64_t b = 59182917008;
uint64_t c = 73624982323;

我需要找到(a * b) % c。如果我直接将a和b相乘，将导致溢出。但是，我无法应用公式(a * b) % c = ((a % c) * (b % c)) % c，因为c > a, c > b以及因此的a % c = a，a % c = b和我将最终再次乘以a和b，这将再次导致溢出。

我如何计算这些变量的这些值（通常是这种情况）的(a * b) % c而不会溢出？

Answer 1

[还有比这更优雅的解决方案，但是一个简单的解决方案就是寻找一个可以处理大量数字的图书馆。它会为您处理对于大多数普通类型而言太大的数字。检查一下：https://gmplib.org/

Answer 2

创建一个类或结构以处理部分数字。

示例伪代码

// operation enum to know how to construct a large number
enum operation {
    case add;
    case sub;
    case mult;
    case divide;
}
class bigNumber {
    //the two parts of the number
    int partA;
    int partB;

    bigNumber(int numA, int numB, operation op) {
        if(op == operation.mult) {
            // place each digit of numA into an integer array
            // palce each digit of numB into an integer array
            // Iteratively place the first half of digits into the partA member
            // Iteratively place the second half of digits into the partB member
        } else if //cases for construction from other operations
    }

    // Create operator functions so you can perform arithmetic with this class
}

uint64_t a =  7940678747;
uint64_t b = 59182917008;
uint64_t c = 73624982323;  

bigNumber bigNum = bigNumber(a, b, .mult);
uint64_t result = bigNum % c;
print(result);

请记住，如果c的值非常小，则可能要生成bigNumber类型的结果。基本上，这只是一个大纲，请确保是否使用不会溢出的类型。

Answer 3

一个简单的解决方案是定义x = 2^32 - 1 = 4.29... 10^9然后将a和b表示为：

a = ka * x + a1 with ka, a1 < x
b = kb * x + b1 with kb, b1 < x

然后

a*b = (ka * x + a1) * (kb * x + b1) = ((ka * kb) * x) * x + x * (b1 * ka) + x * (b2 * kb) + a1 * b1

假设所有操作都在Z / cZ中执行，也就是说，假设在每个操作（*或+）之后执行% c操作，则不需要较大的类型就可以执行所有这些操作