# 擴展歐基里德算法 (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)$ 了

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)$

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`