-1

我有一个问题，a^b mod m可以使用模幂计算，但我遇到的问题是我拥有的 b 值非常大，b > 2^63 - 1所以我们可以修改模幂代码吗

函数模块_pow（基数，指数，模数）
    结果：= 1
    而指数 > 0
        如果（指数模 2 == 1）：
           结果 := (result * base) mod 模数
        指数 := 指数 >> 1
        基数 = (基数 * 基数) mod 模数
    返回结果

容纳这么大的b

还是a^b mod m等于(a^(b mod m)) mod m？

4

1 回答 1

0

a^b mod m=是正确的a^(b mod phi(m)) mod m，其中 phi(m) 是欧拉函数

您的代码也是正确的（如果类型足够长以表示所有值）

您也可以结合两种方法

于 2013-05-05T12:39:43.150 回答