c - C中如何高效验证pow(a, b) % b == a (无溢出)

Question

我想验证一下

pow(a, b) % b == a

在 C 中为真，其中 2 ≤ b ≤ 32768 (2¹⁵) 且 2 ≤ a ≤ b 其中 a 和 b 为整数。

但是，直接计算pow(a, b) % b b 是一个很大的数字，这将很快导致 C 溢出。验证此条件是否成立的技巧/有效方法是什么？

这道题的基础是找到费马小定理的见证，该定理指出如果此条件为假，则 b 不是素数。

另外，我也限制了它可能需要的时间，它不能太慢(接近或超过2秒)。最大的卡迈克尔数，一个数b那不是质数，但也不满足 pow(a, b)% b == a与 2 <= a <= b (b <= 32768)是 29341。因此检查 pow(a, b) % b == a 的方法与 2 <= a <= 29341不应该太慢。

Answer 1

您可以使用 Exponentiation by squaring方法。

思路如下:

• 将b分解为二进制形式并分解乘积
• 请注意，我们始终使用低于 32768 的 %b，因此结果将始终适合 32 位数字。

所以C代码是:

/*
 * this function computes (num ** pow) % mod
 */
int pow_mod(int num, int pow, int mod)
{
    int res = 1

    while (pow>0)
    {
        if (pow & 1)
        {
            res = (res*num) % mod;
        }
        pow /= 2;
        num = (num*num)%mod;
    }

    return res;
}