擴展歐幾里得演算法

擴展歐幾里得演算法（Extended Euclidean algorithm）是歐幾里得演算法（又叫輾轉相除法）的擴展。已知整數a、b，擴展歐幾里得演算法可以在求得a、b的最大公約數的同時，找到整數x、y（其中一個可能是負數），使它們滿足貝祖等式$ax + by = \gcd(a, b)$。如果a是負數，可以把問題轉化成$\left | a \right |(-x) + by = \gcd(|a|, b)$（$\left | a \right |$為a的絕對值），然後令$x'=(-x)$。

在歐幾里得演算法中，我們僅利用了每步帶餘除法所得的餘數。擴展歐幾里得演算法還利用了帶餘除法所得的商，在輾轉相除的同時也能得到貝祖等式中的x、y兩個係數。以擴展歐幾里得演算法求得的係數是滿足裴蜀等式的最簡係數。

另外，擴展歐幾里得演算法是一種自驗證演算法，最後一步得到的$s_{i+1}$和$t_{i+1}$（$s_{i+1}$和$t_{i+1}$的含義見下文）乘以$\gcd(a,b)$後恰為$a$和$b$，可以用來驗證計算結果是否正確。

擴展歐幾里得演算法可以用來計算模逆元，而計算模逆元是RSA加密演算法中生成公鑰、私鑰的必要步驟。

## 演算法和舉例

在標準的歐幾里得演算法中，我們記欲求最大公約數的兩個數為$a,b$，第$i$步帶餘除法得到的商為$q_i$，餘數為$r_{i+1}$，則歐幾里得演算法可以寫成如下形式：

$$\begin{align} r_0 & =a \\ r_1 & =b \\ & \,\,\,\vdots \\ r_{i+1} & =r_{i-1}-q_i r_i \quad \text {且} \quad 0\le r_{i+1} < |r_i| \\ & \,\,\, \vdots \end{align}$$

當某步得到的$r_{i+1}=0$時，計算結束。上一步得到的$r_i$即為$a,b$的最大公約數。

擴展歐幾里得演算法在$q_i$，$r_i$的基礎上增加了兩組序列，記作$s_i$和$t_i$，並令$s_0=1$，$s_1=0$，$t_0=0$，$t_1=1$，在歐幾里得演算法每步計算$r_{i+1}=r_{i-1}-q_i r_i$之外額外計算$s_{i+1}=s_{i-1}-q_i s_i$和$t_{i+1}=t_{i-1}-q_i t_i$，亦即：

$$\begin{align} r_0 & =a & r_1 & =b \\ s_0 & =1 & s_1 & =0 \\ t_0 & =0 & t_1 & =1 \\ & \,\,\,\vdots & & \,\,\,\vdots \\ r_{i+1} & =r_{i-1}-q_i r_i & \text {且} \quad 0 & \le r_{i+1} < |r_i| \\ s_{i+1} & =s_{i-1}-q_i s_i \\ t_{i+1} & =t_{i-1}-q_i t_i \\ & \,\,\, \vdots \end{align}$$

演算法結束條件與歐幾里得演算法一致，也是$r_{i+1}=0$，此時所得的$s_i$和$t_i$即滿足等式$\gcd(a,b)=r_i=as_i+bt_i$。

下表以$a=240$，$b=46$為例演示了擴展歐幾里得演算法。所得的最大公因數是$2$，所得貝祖等式為$\gcd(240,46)=2=-9*240+47*46$。同時還有自驗證等式$|23|*2=46$和$|-120|*2=240$。

序號 i｜商 qi−1｜餘數 ri｜si｜ti

0｜240｜1｜0

1｜46｜0｜1

2｜240 ÷ 46 = 5｜240 − 5 × 46 = 10｜1 − 5 × 0 = 1｜0 − 5 × 1 = −5

3｜46 ÷ 10 = 4｜46 − 4 × 10 = 6｜0 − 4 × 1 = −4｜1 − 4 × −5 = 21

4｜10 ÷ 6 = 1｜10 − 1 × 6 = 4｜1 − 1 × −4 = 5｜−5 − 1 × 21 = −26

5｜6 ÷ 4 = 1｜6 − 1 × 4 = 2｜−4 − 1 × 5 = −9｜21 − 1 × −26 = 47

6｜4 ÷ 2 = 2｜4 − 2 × 2 = 0｜5 − 2 × −9 = 23｜−26 − 2 × 47 = −120

這個過程也可以用初等變換表示。

$\begin{pmatrix}240 & 46\\1 & 0\\0 & 1\end{pmatrix} \rightarrow \begin{pmatrix}10 & 46\\1 & 0\\-5 & 1\end{pmatrix} \rightarrow \begin{pmatrix}10 & 6\\1 & -4\\-5 & 21\end{pmatrix} \rightarrow \begin{pmatrix}4 & 6\\5 & -4\\-26 & 21\end{pmatrix} \rightarrow \begin{pmatrix}4 & 2\\5 & -9\\-26 & 47\end{pmatrix}$

得到$-9\times 240+47\times 46=2$

## 證明

由於$0\le r_{i+1}<|r_i|$，$r_i$序列是一個遞減序列，所以本演算法可以在有限步內終止。又因為$r_{i+1}= r_{i-1} - r_i q_i$， $(r_{i-1}, r_i)$和$(r_{i}, r_{i+1})$的最大公約數是一樣的，所以最終得到的$r_k$是$a$，$b$的最大公約數。

在歐幾里得算法正確性的基礎上，又對於$a=r_0$和$b=r_1$有等式$as_i+bt_i=r_i$成立（i = 0 或 1）。這一關係由下列遞推式對所有$i>1$成立：

$$r_{i+1} = r_{i-1} - r_i q_i = (as_{i-1}+bt_{i-1}) - (as_i+bt_i)q_i = (as_{i-1}-as_iq_i) + (bt_{i-1}-bt_iq_i) = as_{i+1}+bt_{i+1}$$

因此$s_i$和$t_i$滿足裴蜀等式，這就證明了擴展歐幾里得演算法的正確性。

## 實現

以下是擴展歐幾里德演算法的Python實現：

```python
def ext_euclid(a, b):
    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = a, b
    if b == 0:
        return 1, 0, a
    else:
        while(r!=0):
            q = old_r // r
            old_r, r = r, old_r-q*r
            old_s, s = s, old_s-q*s
            old_t, t = t, old_t-q*t
    return old_s, old_t, old_r
```

擴展歐幾里得演算法C++實現：

```c
#include <bits/stdc++.h>
using namespace std;

int ext_euc(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = ext_euc(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

int main()
{
    int a, b, x, y;
    cin >> a >> b;

    ext_euc(a, b, x, y);
    cout << x << ' ' << y << endl;
    return 0;
}
```

## 外部連結

- Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)