快速模冪（fast modular exponentiation）

假設你要算像 7^45 mod 13 這樣的東西。把 7 自乘 45 次、邊乘邊取 mod 13，雖可行但很慢——而在密碼學規模下指數有數百位數，逐一相乘的迴圈永遠跑不完。快速模冪用所謂的反覆平方技巧，只需約 log2(e) 次乘法（而非 e 次）就能算出 a^e mod m。它是讓 RSA、迪菲-赫爾曼（Diffie-Hellman）與米勒-拉賓真正能跑起來的引擎。

其想法是把指數以二進位讀取，並透過平方逐步建出答案。注意 a^(2k) = (a^k)^2 且 a^(2k+1) = a * (a^k)^2。於是你可以掃過 e 的各個位元來算 a^e：維護一個一直在平方的底數（給出 a^1, a^2, a^4, a^8, ...），並在 e 的該位元為 1 時，恰好把結果乘上目前的底數。關鍵是每次乘法與每次平方後都對 m 取模，使數字永不超過約 m^2、保持很小。以 7^13 mod 11 追蹤，13 = 1101（二進位）：起始 result = 1、base = 7。位元 1（個位）：result = 7，base = 49 mod 11 = 5。位元 0：result 仍為 7，base = 25 mod 11 = 3。位元 1：result = 7*3 = 21 mod 11 = 10，base = 9。位元 1：result = 10*9 = 90 mod 11 = 2。所以 7^13 mod 11 = 2，只用 4 輪而非 13 次乘法。

回報非常巨大：執行時間是 O(log e) 次模乘法，把一個數百位元的指數從天文數字般的運算次數壓到幾百次。這正是讓公開金鑰密碼學變得實用之處——你能把一個 2048 位元的數升到一個 2048 位元的次方，只用兩千多次乘法。兩個誠實的提醒：以課本算術做兩個 m 大小數的乘法本身要 O((log m)^2)（用快速乘法會更少），所以總位元成本含這個因子；而且若實作疏忽、每步沒取模，中間值會爆炸到天文大小，整個目的就泡湯了。