分析教材把歐幾里得演算法與快速冪當成 (O(\log n)) 的例子，沒有把它們接成「模意義下的除法」。競賽與密碼學導論裡，這四個是同一條鏈：gcd 判斷互質，擴展版求出係數，係數就是模反元素，快速冪用來算大指數。本篇只做到正確計算與複雜度，不討論如何攻擊實際系統。
相關教材：Chapter2_Algorithm_Analysis_Teaching_Materials.md、Divide_And_Conquer_Teaching_Materials.md。
目錄
1. 歐幾里得演算法
(\gcd(a,b)=\gcd(b, a \bmod b))，直到餘數是 0。另一個數就是最大公因數。
例：(\gcd(252, 105))。
| a | b | a mod b |
|---|---|---|
| 252 | 105 | 42 |
| 105 | 42 | 21 |
| 42 | 21 | 0 |
(\gcd=21)。(252/21=12)，(105/21=5)，確實整除。
除法次數是 (O(\log \min(a,b)))。最慢的是連續費氏數，仍然是對數。這就是分析教材所說的對數型演算法。
負數先取絕對值。(\gcd(0, n)=|n|)，(\gcd(0,0)) 沒有有用的定義，呼叫端不要傳。
2. 擴展歐幾里得
除了 (d=\gcd(a,b))，還求整數 (x,y) 使
[ ax + by = d ]
回代：
[ \begin{align} 252 &= 2\cdot 105 + 42 \ 105 &= 2\cdot 42 + 21 \ 42 &= 2\cdot 21 + 0 \end{align} ]
從 21 往回代：
[ 21 = 105 - 2\cdot 42 = 105 - 2\cdot(252 - 2\cdot 105) = 5\cdot 105 + (-2)\cdot 252 ]
所以 (252\cdot(-2) + 105\cdot 5 = 21)。
實作不要先遞迴再手代。讓遞迴在回來的路上直接組係數：(\gcd(b, a\bmod b)) 得到 (bx_1 + (a\bmod b)y_1 = d)，而 (a\bmod b = a - \lfloor a/b\rfloor b)，整理成 (a) 與 (b) 的係數即可。
3. 模反元素
在模 (m) 下，(a) 的反元素是整數 (a^{-1}) 使 (a\cdot a^{-1} \equiv 1 \pmod m)。它存在若且唯若 (\gcd(a,m)=1)。
那時擴展歐幾里得給出 (ax + my = 1)，所以 (ax \equiv 1 \pmod m)，(x \bmod m) 就是反元素。
例：(a=3)，(m=11)。
[ \begin{align} 11 &= 3\cdot 3 + 2 \ 3 &= 1\cdot 2 + 1 \ 2 &= 2\cdot 1 + 0 \end{align} ]
[ 1 = 3 - 1\cdot 2 = 3 - 1\cdot(11-3\cdot 3) = 4\cdot 3 + (-1)\cdot 11 ]
反元素是 4。檢查：(3\cdot 4=12\equiv 1\pmod{11})。
(\gcd) 不是 1 就沒有反元素。例如 (\gcd(2,4)=2)，不要回傳一個「看起來能乘」的數。費馬小定理 (a^{p-2} \equiv a^{-1}\pmod p) 只在 (p) 是質數且 (p\nmid a) 時可用，那是快速冪的另一條路，模是合數時會悄悄給錯。
4. 快速冪
計算 (a^e \bmod m)。不要先算出巨大的 (a^e) 再取模。
把指數寫成二進位。(13 = 1101_2 = 8+4+1)，所以 (a^{13}=a^8\cdot a^4\cdot a^1)。從 (a) 開始反覆平方，指數的該位元是 1 就把目前的平方乘進答案。每一步都取模。
(3^{13} \bmod 10)：
| 平方 | 值 mod 10 | 指數位元（從低位） | 答案 |
|---|---|---|---|
| (3^1) | 3 | 1 | 3 |
| (3^2) | 9 | 0 | 3 |
| (3^4) | 1 | 1 | 3 |
| (3^8) | 1 | 1 | 3 |
(3^{13}=1594323)，個位數確實是 3。時間 (O(\log e)) 次乘法。底數是矩陣時，同一個演算法就是矩陣快速冪，用來加速線性遞迴，乘法的常數換成矩陣大小。
5. 模運算的幾個恆用規則
設 (m>0)。
[ (x+y)\bmod m = (x\bmod m + y\bmod m)\bmod m ]
[ (x\cdot y)\bmod m = ((x\bmod m)\cdot(y\bmod m))\bmod m ]
減法可能得到負數。程式語言的 % 對負數的符號並不一致。需要非負代表時，寫成 (((x \bmod m)+m)\bmod m)。
除法不是乘上「小數」。模 (m) 下的除以 (a)，是乘上 (a^{-1})，而且只有反元素存在時才合法。
兩個 64 位元整數相乘再取模，若先相乘會溢位。需要「乘法取模」時用更大的寬度，或用專門的無溢位寫法。本篇的範例數字小，不依賴那個技巧。
6. 常見陷阱
gcd(0,0)。 迴圈條件要先定義。- 反元素不存在仍回傳係數。 先看 (\gcd) 是不是 1。
- 快速冪用
int乘int。 即使最後要取模，中間乘積也會溢位。乘法前轉成 64 位元，並在模數大於 (2^{32}) 時改用更寬的乘法。 - 負的指數。 那是反元素加上正指數，不是把迴圈跑負次數。
- 費馬小定理用在合數模。 反元素改走擴展歐幾里得。
- 把本篇算法拿去猜密碼或分解實際金鑰。 正確實作這些函數，和攻擊一個系統，是兩件事。本教材只負責前者。
7. C++ 實作
#include <cstdint>
#include <utility>
long long egcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1, y1;
long long d = egcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return d;
}
long long mod_inverse(long long a, long long m) {
long long x, y;
long long d = egcd(a, m, x, y);
if (d != 1 && d != -1) return -1; // 不存在
return (x % m + m) % m;
}
long long mod_pow(long long a, long long e, long long m) {
long long r = 1 % m;
a %= m;
if (a < 0) a += m;
while (e > 0) {
if (e & 1) r = r * a % m;
a = a * a % m;
e >>= 1;
}
return r;
}egcd 在 a、b 為負時，餘數的符號依 C++ 實作走向零的除法，係數仍滿足等式，但模反元素的入口請先把 a 化成 ([0, m))。
8. 練習題
- 計算 (\gcd(48, 18))，並寫出一組 (48x+18y=\gcd)。
- 11 模 26 的反元素是多少？用乘法檢查。
- (2^{10} \bmod 1000) 用快速冪，平方序列是什麼？
- 為什麼 (\gcd(15, 25)) 算得出係數，卻沒有模 25 的反元素？
- 分析教材說快速冪是 (O(\log N))。主定理的 (a)、(b)、(f(n)) 各是什麼？
參考答案
- (48=2\cdot 18+12)，(18=1\cdot 12+6)，(12=2\cdot 6+0)，所以 (\gcd=6)。回代：(6=18-1\cdot 12=18-1\cdot(48-2\cdot 18)=3\cdot 18 + (-1)\cdot 48)。一組解是 (x=-1, y=3)。
- (\gcd(11,26)=1)。回代得到 (11\cdot(-7)+26\cdot 3=1)。(-7 \bmod 26 = 19)。檢查：(11\cdot 19=209=8\cdot 26+1)。
- 平方序列取模 1000：(2, 4, 16, 256)。(10=1010_2)，所以答案是 (2^8\cdot 2^2 = 256\cdot 4 = 1024 \equiv 24 \pmod{1000})。(2^{16}) 不用算。
- 擴展演算法給的是 (15x+25y=5)，不是 1。模 25 下 15 與 25 不互質，沒有整數乘上 15 會得到 1。
- 每次指數減半、只做一個子問題、再加上常數次乘法：(a=1)，(b=2)，(f(n)=\Theta(1))。這是主定理情況 2，(T(n)=\Theta(\log n))。
小結
歐幾里得演算法用餘數把最大公因數壓到對數時間。擴展版多回傳一組係數。係數在互質時就是模反元素。快速冪用平方把指數的位元變成對數次乘法，每一步取模。四個合在一起，才是模意義下的加減乘除。反元素不存在時要明白回傳失敗，不要用費馬小定理去算合數模。