8

我需要计算a*amodn但a相当大，当我平方它时导致溢出。这样做((a % n)*(a % n)) % n不起作用，因为 (n-1) 2可能溢出。这是在 C++ 中，我正在使用int64_t

编辑：

示例值：a = 821037907258 和 n = 800000000000，如果平方会溢出。

我正在使用 DevCPP，我已经尝试过让大整数库无济于事。

编辑2：

不，这些数字没有规律。

4

5 回答 5

15

如果您不能使用大整数库，并且您没有本机uint128_t（或类似）库，则需要手动执行此操作。

一种选择是表示a为两个 32 位量的总和，即a = 2 32 b + c，其中b包含 32 msb，c包含 32 lsb。平方是一组四个交叉乘法；每个结果都保证适合 64 位类型。然后，您在重新组合各个术语时执行模运算（仔细考虑重新调整所有内容所需的转变）。

于 2012-04-09T16:09:21.800 回答
3

我知道你不再需要这个，并且有一个替代解决方案，但我想添加一个替代方法来实现它。它提供了两种不同的技术：双加算法，以及处理mod(a + b, n)溢出检测的方法。

双加算法通常用于无法进行乘法运算或直接计算成本太高的领域（例如椭圆曲线），但我们可以在我们的情况下采用它来处理它来处理溢出。

以下代码可能比公认的解决方案慢（即使您对其进行了优化），但如果速度不是关键，您可能更喜欢它以使其清晰。

unsigned addmod(unsigned x, unsigned y, unsigned n)
{
    // Precondition: x<n, y<n
    // If it will overflow, use alternative calculation
    if (x + y <= x) x = x - (n - y);
    else x = (x + y) % n;
    return x;
}

unsigned sqrmod(unsigned a, unsigned n)
{
    unsigned b;
    unsigned sum = 0;

    // Make sure original number is less than n
    a = a % n;

    // Use double and add algorithm to calculate a*a mod n
    for (b = a; b != 0; b >>= 1) {
        if (b & 1) {
            sum = addmod(sum, a, n);
        }
        a = addmod(a, a, n);
    }
    return sum;
}
于 2012-04-09T17:30:18.333 回答
1

这是一个乘法的双加实现a * b % m，没有溢出，无论 a、b 和 m 的大小如何。

（请注意，res -= mandtemp_b -= m行依赖于 64 位无符号整数溢出来给出预期的结果。这应该没问题，因为无符号整数溢出在 C 和 C++ 中是明确定义的。因此，使用无符号整数类型很重要。 )

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t res = 0;
    uint64_t temp_b;

    /* Only needed if b may be >= m */
    if (b >= m) {
        if (m > UINT64_MAX / 2u)
            b -= m;
        else
            b %= m;
    }

    while (a != 0) {
        if (a & 1) {
            /* Add b to res, modulo m, without overflow */
            if (b >= m - res) /* Equiv to if (res + b >= m), without overflow */
                res -= m;
            res += b;
        }
        a >>= 1;

        /* Double b, modulo m */
        temp_b = b;
        if (b >= m - b)       /* Equiv to if (2 * b >= m), without overflow */
            temp_b -= m;
        b += temp_b;
    }
    return res;
}

这是我对另一个类似问题的另一个答案的修改。

于 2013-10-29T06:05:05.053 回答
-3

您可以自己实现乘法，每次运行时添加n ，然后立即修改结果。

于 2012-04-09T16:06:55.187 回答
-5

我真的认为这((a % n)*(a % n)) % n应该适用于正整数。为什么你认为它不起作用？你有反例吗？如果 n 可能为负数，则%运算符未定义。

于 2012-04-09T16:25:13.657 回答