擴展歐幾里得算法

擴展歐幾里得算法是歐幾里得算法（又叫輾轉相除法）的擴展。除了計算a、b兩個整數的最大公約數，此算法還能找到整數x、y（其中一個很可能是負數）。通常談到最大公因子時, 我們都會提到一個非常基本的事實: 給予二整數 a 與 b, 必存在有整數 x 與 y 使得ax + by = gcd(a,b)。有兩個數a,b，對它們進行輾轉相除法，可得它們的最大公約數——這是眾所周知的。然後，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。

基本介紹

• 中文名：擴展歐幾里得算法
• 外文名：Extended Euclidean algorithm
• 又叫：輾轉相除法
• 釋義：歐幾里得算法的擴展
• 作用：得到ax+by=gcd(a,b)的整數解
• 學科：計算機

簡介

擴展歐幾里得算法（英語：Extended Euclidean algorithm）是歐幾里得算法（又叫輾轉相除法）的擴展。已知整數a、b，擴展歐幾里得算法可以在求得a、b的最大公約數的同時，能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖等式

如果a是負數，可以把問題轉化成，然後令x'=(-x)。

通常談到最大公約數時，我們都會提到一個非常基本的事實：給予二個整數a、b，必存在整數x、y使得ax + by = gcd(a,b)。

有兩個數a,b，對它們進行輾轉相除法，可得它們的最大公約數——這是眾所周知的。然後，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。

擴展歐幾里得算法可以用來計算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有舉足輕重的地位。

例子

用類似輾轉相除法，求二元一次不定方程47x+30y=1的整數解。

過程可以用矩陣表示（其中q表示商，r表示餘數）。

或者用初等變換

實現

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

def ext_euclid(a, b):         if b == 0:                 return 1, 0, a         else:                 x, y, q = ext_euclid(b, a % b)         # q = gcd(a, b) = gcd(b, a%b)                 x, y = y, (x - (a // b) * y)                 return x, y, q

擴展歐幾里得算法C語言實現：

 int gcdEx(int a,int b,int*x,int*y){    if(b==0)    {        *x=1,*y=0 ;        return a ;    }    else     {        int r=gcdEx(b,a%b,x,y);        /* r = GCD(a, b) = GCD(b, a%b) */        int t=*x ;        *x=*y ;        *y=t-a/b**y ;        return r ;    }}