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

Question

我想验证是否

pow(a, b) % b == a

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

但是如果b很大，直接计算pow(a, b) % b，会很快导致C溢出。 trick/efficient 验证此条件是否成立的方法是什么？

这道题是基于寻找费马小定理的见证，该定理指出如果这个条件为假，b 就不是素数。

另外，我也限制了可能需要的时间，不能太慢（接近或超过2秒）。最大的 Carmichael 数 b 不是素数但也不满足 pow(a, b)% b == a 和 2 <= a <= b（b <= 32768）是 29341。因此检查 [=14 的方法=] 与 2 <= a <= 29341 不应该太慢。

Answer 1

您正在 Z/bZ 中进行模运算。

注意，在商环中，一个元素的class的n次方就是该元素的n次方的class，所以我们有如下结果：

(a^b) mod b = ((((a mod b) * a) mod b) * a) mod b [...] (b times)

因此，您不需要大型整数库。

您可以使用以下算法（伪代码）简单地编写一个 C 程序：

将变量 a 和 b 声明为整数。
使用一个用 a. 初始化的临时变量 temp。
循环 b 步，并在每一步计算 (temp * a) mod b，以获得新的温度值。
将结果与a进行比较

通过这个公式可以看出temp的最大值是32768，所以可以选择一个整数来存储temp。

Answer 2

您可以使用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;
}

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

How to efficiently verify whether pow(a, b) % b == a in C (without overflow)

c

modulus

integer-overflow

memory-efficient