模块化指数

在C / C ++中，如何计算(a^b)%m ，其中b不适合64位？ 换句话说，有没有办法用b%m而不是b来计算上述值？

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

Answer 1

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

a b mod m = a b mod phi(m) mod m

因此，如果b很大，您可以使用值b % phi(m)而不是b 。 phi(m)是Euler的整数函数 ，如果你知道m的素因子分解，就可以很容易地计算出它。

一旦以这种方式减小了b的值，就可以通过平方来计算Ex中的模幂运算O(log (b % phi(m))) 。