擴充歐幾里得演算法

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

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

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

擴充歐幾里得演算法可以用來計算模反元素，求出模反元素是RSA加密演算法中獲得所需公鑰、私鑰的必要步驟。

演算法和舉例

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

${\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{且}}\quad 0\leq r_{i+1}<|r_{i}|\\&\,\,\,\vdots \end{aligned}}}$

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

擴充歐幾里得演算法在${\displaystyle q_{i}}$，${\displaystyle r_{i}}$的基礎上增加了兩組序列，記作${\displaystyle s_{i}}$和${\displaystyle t_{i}}$，並令${\displaystyle s_{0}=1}$，${\displaystyle s_{1}=0}$，${\displaystyle t_{0}=0}$，${\displaystyle t_{1}=1}$，在歐幾里得演算法每步計算${\displaystyle r_{i+1}=r_{i-1}-q_{i}r_{i}}$之外額外計算${\displaystyle s_{i+1}=s_{i-1}-q_{i}s_{i}}$和${\displaystyle t_{i+1}=t_{i-1}-q_{i}t_{i}}$，亦即：

${\displaystyle {\begin{aligned}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{且}}0&\leq 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{aligned}}}$

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

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

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

${\displaystyle {\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}}}$^[3]

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

證明

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

在歐幾里得演算法正確性的基礎上，又對於${\displaystyle a=r_{0}}$和${\displaystyle b=r_{1}}$有等式${\displaystyle as_{i}+bt_{i}=r_{i}}$成立（i = 0 或 1）。這一關係由下列遞推式對所有${\displaystyle i>1}$成立：

${\displaystyle 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_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1}+bt_{i+1}}$

因此${\displaystyle s_{i}}$和${\displaystyle t_{i}}$滿足貝祖等式，這就證明了擴充歐幾里得演算法的正確性。

實現

以下是擴充歐幾里德演算法的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++實現：

#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;
}

參考資料

1. 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25]. （原始內容存檔 (PDF)於2021-01-24） （中文（臺灣））.
2. Kenneth H.Rosen; 徐六通 楊娟 吳斌 譯. 离散数学及其应用 原書第七版. 2015-01-01: 232頁. ISBN 978-7-111-45382-6. 引文使用過時參數coauthors (幫助)
3. 張慧玲. 介紹多項式帶餘除法的矩陣形式及其應用. 太原大學教育學院學報. 2014, (1): 第103–105頁 [2016-03-02]. （原始內容存檔於2022-12-14）.

參考文獻

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 演算法導論, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.
• Christof Paar,Jan Pelzl著 馬小婷 譯. 深入淺出密碼學, 清華大學出版社, ISBN 9787302296096. Pages 151-155 6.3.2 擴充的歐幾里得演算法

外部連結

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) （頁面存檔備份，存於互聯網檔案館）