擴充歐幾里得演算法(英語:Extended Euclidean algorithm)是歐幾里得演算法(又叫輾轉相除法)的擴充。已知整數a、b,擴充歐幾里得演算法可以在求得a、b的最大公因數的同時,找到整數x、y(其中一個可能是負數),使它們滿足貝祖等式
。[1]如果a是負數,可以把問題轉化成
(
為a的絕對值),然後令
。
在歐幾里得演算法中,我們僅利用了每步帶餘除法所得的餘數。擴充歐幾里得演算法還利用了帶餘除法所得的商,在輾轉相除的同時也能得到貝祖等式[2]中的x、y兩個係數。以擴充歐幾里得演算法求得的係數是滿足貝祖等式的最簡係數。
另外,擴充歐幾里得演算法是一種自驗證演算法,最後一步得到的
和
(
和
的含義見下文)乘以
後恰為
和
,可以用來驗證計算結果是否正確。
擴充歐幾里得演算法可以用來計算模反元素,求出模反元素是RSA加密演算法中獲得所需公鑰、私鑰的必要步驟。
演算法和舉例
在標準的歐幾里得演算法中,我們記欲求最大公因數的兩個數為
,第
步帶餘除法得到的商為
,餘數為
,則歐幾里得演算法可以寫成如下形式:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/634659efd108de338669a1f686a849b72c1ba13d)
當某步得到的
時,計算結束。上一步得到的
即為
的最大公因數。
擴充歐幾里得演算法在
,
的基礎上增加了兩組序列,記作
和
,並令
,
,
,
,在歐幾里得演算法每步計算
之外額外計算
和
,亦即:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f82eafdd1e1ba902b81e319f1d162b8abeb3ff7)
演算法結束條件與歐幾里得演算法一致,也是
,此時所得的
和
即滿足等式
。
下表以
,
為例演示了擴充歐幾里得演算法。所得的最大公因數是
,所得貝祖等式為
。同時還有自驗證等式
和
。
序號 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
|
這個過程也可以用初等變換表示。
[3]
得到
證明
由於
,
序列是一個遞減序列,所以本演算法可以在有限步內終止。又因為
,
和
的最大公因數是一樣的,所以最終得到的
是
,
的最大公因數。
在歐幾里得演算法正確性的基礎上,又對於
和
有等式
成立(i = 0 或 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/725a56b6802164bfe141031595faa828ba50dd05)
因此
和
滿足貝祖等式,這就證明了擴充歐幾里得演算法的正確性。
實現
以下是擴充歐幾里德演算法的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;
}
參考資料
參考文獻
外部連結