# 擴展歐基里德算法 (Extended Euclidean algorithm) ## 歐基里德算法 歐基里德算法又稱輾轉相除法，是計算兩個整數的最大公因數(Greatest Common Divisor, GCD)的方法。 有兩個數字 $a, b$，令 $p = gcd(a, b)$，那麼一定存在兩個正整數 $n, m \in \mathbb{R}$ 使得 $$ a = np,\quad b = mp $$ 那麼如果要求 $p$，我們可以不斷讓 $a, b$ 互減，最後就會剩下 $p$ 下圖是從維基百科上抓來的，兩線段分別表示 $252$ 及 $105$，每個單位為其最大公因數 $21$ <center> <img src="https://i.imgur.com/XYw4kc5.gif" height=300> </center> 可以發現到，當我們重複將較大的一方扣除較小的一方，直到其中一方為 $0$ 時，剩下的就會剛好是最大公因數 $p$ 從這裡我們可以發現到，最大公因數實際上有這樣的性質: $$ gcd(a, b) = \begin{cases} gcd(a-b, b) & a > b \\ gcd(b-a, a) & a < b \end{cases} $$ 不過實際上我們也不需要做那麼多次減法，因為我們總是會減到直到不能再減 - 假設 $a > b$，那麼 $a - b$ 的次數就是 $\lfloor a/b \rfloor$，而這最後的 $a$ 其實就是 $a\%b$ - 假設 $a < b$，那麼 $b - a$ 的次數就是 $\lfloor b/a \rfloor$，而這最後的 $b$ 其實就是 $b\%a$ > 附註: $\lfloor \rfloor$ 為下高斯符號，也就是向下取整 > 舉例來說: $\lfloor 3.14 \rfloor = 3, \lfloor 4.9 \rfloor = 4$ > 附註: 雖然沒有提到 $a=b$ 的情況，不過在 $a=b$ 時無論放在 $a > b$ 的作法或是 $a < b$ 的做法也都會是正確的 也就是說: $$ gcd(a, b) = \begin{cases} gcd(a\%b, b) & a > b \\ gcd(b\%a, a) & a < b \end{cases} $$ 換個方法敘述 已知 $a/b = q \dots r$ $$ a = qb + r\\ gcd(a, b) = gcd(qb + r, b) = gcd(r, b) = gcd(a\%b, b) $$ 已知 $b/a = q \dots r$ $$ b = qa + r\\ gcd(a, b) = gcd(qa + r, a) = gcd(r, a) = gcd(b\%a, a) $$ 在實作上，可以透過 $gcd(a, b) = gcd(b, a\%b)$ 來簡寫 如果 $a < b$ 的話，因為 $gcd(b, a\%b)$ 會將兩者交換，因此下一次計算 $gcd$ 時就會計算到 $gcd(a, b\%a)$ 了 ```python= def gcd(a, b): if(b == 0): return a return gcd(b, a%b) ``` ## 擴展歐基里德算法 擴展歐基里德算法的命題如下: 已知 $\forall a, b \in \mathbb{Z}$，必定存在 $x, y$ 使得貝祖定理成立 $$ ax + by = gcd(a, b) $$ 求 $x, y$ 分別為何 根據命題可得 $$ \begin{align*} ax_1 + by_1 &= gcd(a, b) \\ bx_2 + (a\%b)y_2 &= gcd(b, a\%b) \end{align*} $$ 又因為 $$ gcd(a, b) = gcd(b, a\%b) $$ 因此 $$ \begin{align*} ax_1 + by_1 &= bx_2 + (a\%b)y_2 \\ &= bx_2 + (a-\lfloor a/b \rfloor b)y_2 \end{align*} $$ 整理式子後可以得到 $$ ax_1 + by_1 = ay_2 + b(x_2 - \lfloor a/b \rfloor y_2) $$ 因此 $$ \begin{cases} x_1 = y_2 \\ y_1 = x_2 - \lfloor a/b \rfloor y_2 \end{cases} $$ 因此，由於 $gcd(a, b) = gcd(b, a\%b)$，我們可以將原問題轉換成等價的新問題，並且新問題得出來的 $x, y$ 可以幫助我們得到原問題的 $x, y$ 如此一來就可以實作出擴展歐基里德算法囉! > 補充: 在 $b = 0$ 的情況下我們知道 $a = 1 \times a + 0 \times b$，因此回傳 $(x, y) = (1, 0)$ ```python= def exd_gcd(a, b): if(b == 0): return 1, 0 else: x, y = exd_gcd(b, a%b) return y, x-(a//b)*y ``` ###### tags: `Crypto`