擴展歐幾里得算法

擴展歐幾里得算法歐幾里得算法(又叫輾轉相除法)的擴展。除了計算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 ;    }}

相關詞條

熱門詞條

聯絡我們