擴展歐幾里得演算法計算機

擴展歐幾里得演算法計算機可計算兩個整數的最大公因數 (GCD)，並尋找 Bézout 係數——即滿足 gcd(a, b) = s·a + t·b 的整數 s 和 t。除了計算 GCD 外，此工具還提供全動畫的逐步除法表、回代過程和模反元素計算，非常適合數論課程、密碼學研究和競賽程式設計。

什麼是擴展歐幾里得演算法？

擴展歐幾里得演算法 (EEA) 是歐幾里得經典 GCD 演算法的延伸。基本演算法透過連續除法尋找 gcd(a, b)，而擴展版本則同時追蹤兩個整數序列，記錄每個餘數如何表示為原始輸入的線性組合。

演算法原理

EEA 在每個除法步驟中維護三組值 — (r, s, t)：

1. 初始化：r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. 每一步：計算商 q = ⌊rₙ₋₁ / rₙ⌋，然後更新 rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. 當餘數為 0 時停止；上一個餘數即為 gcd(a, b)
4. 對應的 s 和 t 值即為 Bézout 係數

逐步範例：gcd(252, 105)

結果：gcd(252, 105) = 21，Bézout 等式為：21 = 1 × 252 + (−2) × 105。您可以使用上方的計算機嘗試獲取確切係數。

擴展歐幾里得演算法的應用

1. 模反元素（密碼學）

最重要的應用是計算模反元素。如果 gcd(a, m) = 1，則 Bézout 係數 s 滿足：

模反元素在 RSA 加密（計算私鑰指數 d）、Diffie-Hellman 金鑰交換和橢圓曲線密碼學中至關重要。

2. 求解線性丟番圖方程

方程 ax + by = c 有整數解當且僅當 gcd(a, b) 能整除 c。若是如此，一組特解為 x₀ = s·(c/d), y₀ = t·(c/d)，其中 d = gcd(a, b)，s, t 為 Bézout 係數。

3. 中國剩餘定理

EEA 用於中國剩餘定理的構造性證明和計算 — 尋找滿足 x ≡ a₁ (mod m₁) 和 x ≡ a₂ (mod m₂) 的 x — 透過計算模數的模反元素來實現。

4. 分數簡約與最小公倍數

gcd(a, b) = 1 確認 a/b 已經是既約分數。最小公倍數為 lcm(a, b) = |a·b| / gcd(a, b)。

Bézout 係數並非唯一

Bézout 係數 s 和 t 並非唯一的。如果 (s, t) 是一組解，那麼對於任何整數 k，(s + k·(b/d), t − k·(a/d)) 也是一組解，其中 d = gcd(a, b)。EEA 返回的是滿足 |s| ≤ |b/d| 且 |t| ≤ |a/d| 的解。

時間複雜度

擴展歐幾里得演算法運行 O(log min(a, b)) 次迭代 — 與基本歐幾里得演算法相同。根據拉梅定理 (Lamé's theorem)，步驟數永遠不會超過較小輸入數字位數的 5 倍。這使得它即使對於密碼學應用中使用的大整數也非常高效。

常見問題解答

什麼是擴展歐幾里得演算法？

擴展歐幾里得演算法擴展了歐幾里得 GCD 演算法，以同時計算滿足 gcd(a, b) = s·a + t·b 的 Bézout 係數 s 和 t。它追蹤除法過程中每個餘數如何表示為 a 和 b 的線性組合。

什麼是 Bézout 係數？

Bézout 係數是根據 Bézout 等式（數論中的一個定理）保證存在的整數 s 和 t。它們滿足 gcd(a, b) = s·a + t·b，並由擴展歐幾里得演算法高效計算。它們用於模反元素計算、求解丟番圖方程和中國剩餘定理。

如何使用擴展歐幾里得演算法尋找模反元素？

如果 gcd(a, b) = 1（a 和 b 互質），則 Bézout 係數 s 滿足 s·a ≡ 1 (mod b)。a 模 b 的模反元素即為 s mod b（調整為正數）。本計算機會在結果中直接顯示此項。

模反元素在什麼時候不存在？

a 模 m 的模反元素存在當且僅當 gcd(a, m) = 1。如果 gcd(a, m) > 1，則沒有整數 x 滿足 a·x ≡ 1 (mod m)。

擴展歐幾里得演算法的時間複雜度是多少？

O(log min(a, b)) 次除法，與基本歐幾里得演算法相同。根據拉梅定理，步驟數受限於較小輸入數字位數的 5 倍，因此效率極高。

其他資源

• 擴展歐幾里得演算法 - 維基百科
• Bézout 等式 - 維基百科
• 模反元素 - 維基百科