模块求幂

问题描述：

在C/C++中，我该如何计算(a^b)%m，其中b不适合64位？换句话说，是否有使用b%m而不是b来计算上述值的方法？模块求幂

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

这似乎更像是一个数学问题。 – 2012-07-12 09:19:41

请尝试http://math.stackexchange.com/ – 2012-07-12 09:19:58

你的意思是说b不适合64位？通常的指数运算法则是，如果b的下一位被设置，然后进行平方，则通过乘以a来累加结果。对于大b来说这似乎相当容易，大a和m很难。 – tbroberg 2012-07-12 09:35:52

答

据Euler's theorem，如果a和m互质：

a^b mod m = a^{b mod phi(m)} mod m

所以如果b较大，则可以使用值b % phi(m)而不是b。 phi(m)是Euler's totient function，如果知道m的素因分解，可以很容易地计算出来。

以这种方式减少了b的值后，使用Exponentiation by squaring来计算O(log (b % phi(m)))中的模数求幂。

挑选：只有当a和m是互质时，这才是真实的。 – Henrik 2012-07-12 10:02:20

@Henrik：这意味着即使m是素数和a sabari 2012-07-12 10:06:13

@亨利克：对，我忘记了，谢谢。 sabari：是的，它会在这种情况下起作用。 – interjay 2012-07-12 10:07:18