c - 模幂

Question

(a^b)%m在 C/C++中，如何计算b不适合 64 位的位置？换句话说，有没有一种方法可以使用b%m而不是计算上述值b？

O(log(b))是否有任何算法可以按时间或时间计算上述结果O(log(b%m))？

Answer 1

根据欧拉定理，如果a和m互质：

ab mod m = ab mod phi(m) mod m

所以如果b很大，您可以使用该值b % phi(m)而不是b. phi(m)是欧拉的总函数，如果您知道 的素数分解，就可以很容易地计算出m。

一旦你b以这种方式减少了 的值，就可以使用Exponentiation by squareing来计算 中的模幂O(log (b % phi(m)))。