如何有效地验证pow(a,b)%b == a in C(无溢出)

Question

我想验证是否

pow(a,b)%b == a

在C中为真,2≤b≤32768(2 ¹⁵)且2≤a≤b,a和b为整数.

但是,直接计算pow(a, b) % bb是一个大数字,这将很快导致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.

这个想法如下:

• 分解b以二进制形式和分解产物
• 请注意,我们总是使用%b低于32768的值,因此结果总是适合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;
}