本页使用了标题或全文手工转换

扩展欧几里得算法

维基百科,自由的百科全书
跳转至: 导航搜索

扩展欧几里得算法英语:Extended Euclidean algorithm)是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足貝祖等式

如果a是负数,可以把问题转化成

为a的绝对值),然后令

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

有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

扩展欧几里得算法可以用来计算模反元素(也叫模逆元),而模反元素在RSA加密算法中有举足轻重的地位。

例子[编辑]

用类似辗转相除法,求二元一次不定方程的整数解。

然后把它们改写成“余数等于”的形式

  • //式1
  • //式2
  • //式3

然后把它们“倒回去”

  • //应用式3
  • //应用式2
  • //应用式1

得解

这个过程可以用矩阵表示(其中q表示商,r表示余数)

或者用初等变换

[2]

实现[编辑]

以下是扩展欧几里德算法的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;
     }
 }

参考资料[编辑]

  1. ^ 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25] (中文(台灣)‎). 
  2. ^ 张慧玲. 介绍多项式带余除法的矩阵形式及其应用. 太原大学教育学院学报. 2014, (1): 第103–105页. 

參考文獻[编辑]

外部連結[编辑]