模塊求冪

在C/C++中，我該如何計算(a^b)%m，其中b不適合64位？換句話說，是否有使用b%m而不是b來計算上述值的方法？模塊求冪

是否有任何算法可以計算出上述結果O(log(b))時間或O(log(b%m))時間？

2012-07-12 sabari

這似乎更像是一個數學問題。 – 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)))中的模數求冪。

2012-07-12 09:54:40 interjay

挑選：只有當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

回答