為何數論屬於本階
前三篇指南活在平面上——方向測試、凸包、掃描線。本篇離開幾何走向算術，但精神完全一樣：拿一個「看起來」必定昂貴的運算，找出讓它變便宜的結構。這裡的兩個運算是：計算兩個整數的最大公因數（GCD），以及計算 a^e mod m——一個底數升到巨大的指數、再對 m 取模。兩者聽來無害，卻是 RSA 與幾乎每一種公鑰方案的跳動心臟，所以讓它們真正快速且可證明正確，絕非紙上談兵。
一開始就要說一個關鍵的誠實點。當我們衡量這些演算法時，我們是用輸入的「位數」來計算規模，而不是它的數值。一個約一千位元的數 m 大得驚人——遠超過 2^1000——但它的輸入規模卻只有約 1000。一個執行時間與 m 本身成正比的演算法會毫無希望；那會是輸入長度的指數時間。底下的一切之所以快，正是因為它們的執行時間是位數的多項式，對這些問題而言大致就是 O(log 那些數字)。把一個數的「數值」和它的「描述規模」搞混，是這個子題裡最常見的陷阱。
歐幾里得演算法：靠餘數縮小
a 與 b 的最大公因數是同時整除兩者的最大整數。天真的做法——從 min(a, b) 往下試每個候選——花費的時間與數字的數值成正比，我們剛看到那是其規模的指數時間。歐幾里得的構想已有兩千多年歷史，只有一行：gcd(a, b) = gcd(b, a mod b)，重複到第二個引數變成 0 為止，此時第一個引數就是答案。為何可以把 a 換成 a mod b？因為 a 與 b 的任何公因數也整除 a mod b = a - (a div b) * b，反之亦然；公因數的「集合」在這個替換下不變，所以最大的那個也不變。即使數字在縮小，最大公因數始終是這個迴圈的不變量。
為何它快？看 gcd(48, 30) 的追蹤：48 mod 30 = 18，於是 gcd(30, 18)；30 mod 18 = 12，於是 gcd(18, 12)；18 mod 12 = 6，於是 gcd(12, 6)；12 mod 6 = 0，於是 gcd(6, 0) = 6。每一步餘數都下降，但更深的事實是：「兩」個連續步驟至少會把較大的數減半：若 b <= a，則 a mod b < b，而且 a mod b < a/2（要嘛 b <= a/2，要嘛 b > a/2 而此時 a mod b = a - b < a/2）。每兩步把數字減半，意味著總共 O(log a) 步——這正是讓二分搜尋變快的同一種對數式縮減，只是由一條截然不同的路徑抵達。
擴展歐幾里得：連係數一起拿到
單純的歐幾里得告訴你最大公因數「是什麼」；擴展歐幾里得演算法還告訴你如何用 a 與 b「把它組出來」。它回傳的不只是 g = gcd(a, b)，還有兩個整數 x 與 y 解出貝祖等式：a*x + b*y = g。訣竅是把係數沿著遞迴往上帶回。在基底情形 gcd(g, 0) = g，我們可以寫成 g = 1*g + 0*0。接著在每次回傳時，若較深的呼叫對 gcd(b, a mod b) 給了係數 (x', y')，一點代數就能把它們改寫成 gcd(a, b) 的係數 (y', x' - (a div b)*y')。往下一趟、往上一趟——仍是 O(log a) 步。
為何要在意 x 與 y？因為它們把模反元素交到你手上，那個讓模算術感覺像普通分數的運算。當 gcd(a, m) = 1 時，擴展歐幾里得會產生 x 與 y 使得 a*x + m*y = 1。把它對 m 取模來讀：m*y 那一項消失，剩下 a*x = 1 (mod m)。所以 x 就是 a 在模 m 下的乘法反元素——你乘上它就等於在模 m 算術裡「除以 a」的那個數。除非 gcd(a, m) = 1，否則反元素不存在，而擴展歐幾里得既能偵測這個條件（它回傳 g != 1），在成立時又順手免費算出反元素。正是這一個事實，讓 RSA 得以解密。
- 基底情形：gcd(g, 0) 回傳 (g, 1, 0)，意思是 g = 1*g + 0*0。
- 遞迴步驟：對 (b, a mod b) 呼叫擴展歐幾里得，得到 (g, x', y')。
- 回程時合併：回傳 (g, y', x' - (a div b) * y') 作為 (a, b) 的係數。
- 若 g = 1 且 m 是第二個輸入，第一個回傳的係數就是 a 在模 m 下的反元素。
用反覆平方做模冪
現在輪到第二匹主力：計算 a^e mod m，其中 e 可能有數百位元。天真的迴圈把 a 乘進一個累積乘積 e 次——但 e 可能是 2^1000，那個迴圈在宇宙的壽命裡都跑不完；它是 e 的規模的指數時間。快速模冪，又叫反覆平方法或平方並乘法，只用 O(log e) 次乘法就完成。構想是用「加倍」而非「相加」來蓋出乘冪：a^1, a^2, a^4, a^8, …，每個都由前一個平方而來。既然任何指數 e 都是若干 2 的乘冪之和（也就是它的二進位數字），a^e 就是恰好那些「該位元為 1」的平方乘冪的乘積。
power(a, e, m): # compute a^e mod m
result = 1
a = a mod m
while e > 0:
if e is odd: # this binary digit of e is 1
result = (result * a) mod m
a = (a * a) mod m # square the running power
e = e div 2 # drop the digit we just used
return result這個迴圈對 e 的每個位元跑一次，所以是 O(log e) 次迭代，每次做一兩次模 m 的乘法——這就是全部的加速，用「位數的線性時間」處理了指數級的數值。每一行裡的「mod m」和平方一樣重要：沒有它，累積乘冪 a^(2^k) 會長到數十億位，每次乘法本身就會爆掉。每次運算後都對 m 取模，能讓每個中間值都低於 m，所以每次乘法都維持成至多 log m 位元的固定規模運算。速度來自兩個構想協同運作：乘法次數少（平方並乘法）與運算元小（每次都取模）。
正確性是一段乾淨的歸納，並呼應了基礎階養成的迴圈不變量習慣。守住這個不變量：在每次迭代開頭，result * a^e（用 result、a、e 的當前值）等於原始的 a0 升到原始的 e0，全部對 m 取模。它一開始為真（result = 1, a = a0, e = e0）。每次迭代都保持它：當 e 為偶時，把 a 平方並把 e 減半會讓 a^e 不變；當 e 為奇時，把 result 乘上 a 恰好吸收了那個剩下的因子。當 e 抵達 0，a^e = 1，所以單單 result 就等於 a0^e0 mod m。順帶一提，這套「靠加倍來平方」的模式，在任何乘法滿足結合律的場合都能算高次冪——矩陣、多項式——不只是整數模 m。
這一切通往何處：RSA 與接下來
把這些零件拼起來，你就能讀懂 RSA 的演算法核心。公鑰用快速模冪算 c = x^e mod m 來加密訊息 x；配對的私鑰用 c^d mod m 解密，其中指數 d 是 e 的模反元素（模一個由 m 的質因數導出的量），由擴展歐幾里得求出。兩個方向都不過是反覆平方；金鑰生成不過是最大公因數與反元素。其安全性並非建立在這些運算之中任何一個很慢，而是建立在一道不同的鴻溝上：加密容易，而在不知道 m 的因式分解下「回推」秘密指數卻看似困難。注意這個謹慎的措辭——「看似困難」反映的是目前不知道有效率的因式分解演算法，這和「證明沒有任何這種演算法存在」並不相同。
本階的最後一篇指南承接從這裡開始的兩條線索。第一，巨大整數與多項式的乘法，FFT 在此擊敗了課本式的 O(n^2)——正是你在卡拉楚巴乘法見過的那套分治反射，推進到 O(n log n)。第二，我們一直在對某個 m 取模做乘冪，卻沒問 m 是否為質數；米勒-拉賓測試用模冪本身作為探針來快速判定質數，而它是個蒙地卡羅演算法——它可能以可控的機率出錯，這個取捨我們會誠實地衡量。兩者都直接倚靠你剛建好的反覆平方引擎。