好的，所以你要計算a^b mod m。首先，我們將采取一種天真的方法，然后看看我們如何改進它。

首先，減少a mod m。這意味著，找到一個數字，a1以便0 <= a1 < m和a = a1 mod m。然后在一個循環中重復乘以a1并再次減少mod m。因此，在偽代碼中：

a1 = a reduced mod m

p = 1

for(int i = 1; i <= b; i++) {

    p *= a1

    p = p reduced mod m

}

通過這樣做，我們避免大于的數字m^2。這是關鍵。我們避免數字大于的原因m^2是因為在每一步0 <= p < m和0 <= a1 < m。

舉個例子，讓我們來計算吧5^55 mod 221。首先，5已經減少了mod 221。

1 * 5 = 5 mod 221

5 * 5 = 25 mod 221

25 * 5 = 125 mod 221

125 * 5 = 183 mod 221

183 * 5 = 31 mod 221

31 * 5 = 155 mod 221

155 * 5 = 112 mod 221

112 * 5 = 118 mod 221

118 * 5 = 148 mod 221

148 * 5 = 77 mod 221

77 * 5 = 164 mod 221

164 * 5 = 157 mod 221

157 * 5 = 122 mod 221

122 * 5 = 168 mod 221

168 * 5 = 177 mod 221

177 * 5 = 1 mod 221

1 * 5 = 5 mod 221

5 * 5 = 25 mod 221

25 * 5 = 125 mod 221

125 * 5 = 183 mod 221

183 * 5 = 31 mod 221

31 * 5 = 155 mod 221

155 * 5 = 112 mod 221

112 * 5 = 118 mod 221

118 * 5 = 148 mod 221

148 * 5 = 77 mod 221

77 * 5 = 164 mod 221

164 * 5 = 157 mod 221

157 * 5 = 122 mod 221

122 * 5 = 168 mod 221

168 * 5 = 177 mod 221

177 * 5 = 1 mod 221

1 * 5 = 5 mod 221

5 * 5 = 25 mod 221

25 * 5 = 125 mod 221

125 * 5 = 183 mod 221

183 * 5 = 31 mod 221

31 * 5 = 155 mod 221

155 * 5 = 112 mod 221

112 * 5 = 118 mod 221

118 * 5 = 148 mod 221

148 * 5 = 77 mod 221

77 * 5 = 164 mod 221

164 * 5 = 157 mod 221

157 * 5 = 122 mod 221

122 * 5 = 168 mod 221

168 * 5 = 177 mod 221

177 * 5 = 1 mod 221

1 * 5 = 5 mod 221

5 * 5 = 25 mod 221

25 * 5 = 125 mod 221

125 * 5 = 183 mod 221

183 * 5 = 31 mod 221

31 * 5 = 155 mod 221

155 * 5 = 112 mod 221

因此，5^55 = 112 mod 221。

現在，我們可以通過使用取冪進行平方來改善這一點; 這是著名的技巧，其中我們將求冪減少到只需要log b乘法而不是b。請注意，使用上面描述的算法，通過平方改進進行求冪，最終得到了從右到左的二進制方法。

a1 = a reduced mod m

p = 1

while (b > 0) {

     if (b is odd) {

         p *= a1

         p = p reduced mod m

     }

     b /= 2

     a1 = (a1 * a1) reduced mod m

}

因此，因為55 = 110111二進制

1 * (5^1  mod 221) = 5 mod 221

5 * (5^2  mod 221) = 125 mod 221

125 * (5^4  mod 221) = 112 mod 221

112 * (5^16  mod 221) = 112 mod 221

112 * (5^32  mod 221) = 112 mod 221

所以答案是5^55 = 112 mod 221。這有效的原因是因為

55 = 1 + 2 + 4 + 16 + 32

以便

5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221

     = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221

     = 5 * 25 * 183 * 1 * 1 mod 221

     = 22875 mod 221

     = 112 mod 221

在我們計算步驟5^1 mod 221，5^2 mod 221等我們注意到5^(2^k)= 5^(2^(k-1)) * 5^(2^(k-1))因為2^k = 2^(k-1) + 2^(k-1)這樣我們就可以首先計算5^1和減少mod 221，那么這個平方和降低mod 221以獲得5^2 mod 221等

上述算法形式化了這個想法。

您可以使用指數的二進制擴展來加快進程（這可能對非常大的指數有用）。首先計算5,5 ^ 2,5 ^ 4,5 ^ 8 mod 221 - 你通過重復平方來做到這一點：

?5^1 = 5(mod 221)

?5^2 = 5^2 (mod 221) = 25(mod 221)

?5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)

?5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)

5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)

5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)

現在我們可以寫了

55 = 1 + 2 + 4 + 16 + 32

so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32?

? ? ? ? = 5? ?* 25? * 625 * 1? ? * 1 (mod 221)

? ? ? ? = 125 * 625 (mod 221)

? ? ? ? = 125 * 183 (mod 183) - because 625 = 183 (mod 221)

? ? ? ? = 22875 ( mod 221)

? ? ? ? = 112 (mod 221)

你可以看到非常大的指數如何更快（我相信它是log而不是b中的線性，但不確定。）

/* The algorithm is from the book "Discrete Mathematics and Its

   Applications 5th Edition" by Kenneth H. Rosen.

   (base^exp)%mod

*/

int modular(int base, unsigned int exp, unsigned int mod)

{

    int x = 1;

    int power = base % mod;

    for (int i = 0; i < sizeof(int) * 8; i++) {

        int least_sig_bit = 0x00000001 & (exp >> i);

        if (least_sig_bit)

            x = (x * power) % mod;

        power = (power * power) % mod;

    }

    return x;

}