扩展欧几里得算法

关注
扩展欧几里得算法www.shan-machinery.com

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

ax+by=gcd(a,b).{\displaystyle ax+by=\gcd(a,b).}

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

|a|(−x)+by=gcd(|a|,b){\displaystyle \left|a\right|(-x)+by=\gcd(|a|,b)}(|a|{\displaystyle \left|a\right|}为a的绝对值),然后令x′=(−x){\displaystyle x'=(-x)}

通常谈到最大公因数时,我们都会提到一个非常基本的事实(由贝祖定理给出):给定二个整数a、b,必存在整数x、y使得ax + by = gcd(a,b)[1]。

众所周知,已知两个数a{\displaystyle a}和b{\displaystyle b},对它们进行辗转相除(欧几里得算法),可得它们的最大公约数。不过,在欧几里得算法中,我们仅仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商,在辗转相除的同时也能得到贝祖等式[2](贝祖定理中描述的等式)中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。

另外,扩展欧几里得算法是一种自验证算法,最后一步得到的si+1{\displaystyle s_{i+1}}和ti+1{\displaystyle t_{i+1}}(si+1{\displaystyle s_{i+1}}和ti+1{\displaystyle t_{i+1}}的含义见下文)乘以gcd(a,b){\displaystyle \gcd(a,b)}后恰为a{\displaystyle a}和b{\displaystyle b},可以用来验证计算结果是否正确。

扩展欧几里得算法可以用来计算模反元素(也叫模逆元),求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。

目录1 算法和举例2 证明3 实现4 参考资料5 参考文献6 外部链接算法和举例[编辑]

在标准的欧几里得算法中,我们记欲求最大公约数的两个数为a,b{\displaystyle a,b},第i{\displaystyle i}步带余除法得到的商为qi{\displaystyle q_{i}},余数为ri+1{\displaystyle r_{i+1}},则欧几里得算法可以写成如下形式:

r0=ar1=b⋮ri+1=ri−1−qiriand0≤ri+11−qiri{\displaystyle r_{i+1}=r_{i-1}-q_{i}r_{i}}之外额外计算si+1=si−1−qisi{\displaystyle s_{i+1}=s_{i-1}-q_{i}s_{i}}和ti+1=ti−1−qiti{\displaystyle t_{i+1}=t_{i-1}-q_{i}t_{i}},亦即:

r0=ar1=bs0=1s1=0t0=0t1=1⋮⋮ri+1=ri−1−qiriand 0≤ri+1qisiti+1=ti−1−qiti⋮{\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{and }}0&\leq r_{i+1}240+47∗46{\displaystyle \gcd(240,46)=2=-9*240+47*46}。同时还有自验证等式|23|∗2=46{\displaystyle |23|*2=46}和|−120|∗2=240{\displaystyle |-120|*2=240}

序号 i商 qi−1 余数 risi ti024010146012240 ÷ 46 = 5240 − 5 × 46 = 101 − 5 × 0 = 10 − 5 × 1 = −5346 ÷ 10 = 446 − 4 × 10 = 60 − 4 × 1 = −41 − 4 × −5 = 21410 ÷ 6 = 110 − 1 × 6 = 41 − 1 × −4 = 5−5 − 1 × 21 = −2656 ÷ 4 = 16 − 1 × 4 = 2−4 − 1 × 5 = −921 − 1 × −26 = 4764 ÷ 2 = 24 − 2 × 2 = 05 − 2 × −9 = 23−26 − 2 × 47 = −120证明[编辑]

由于0≤ri+1riqi{\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}}, (ri−1,ri){\displaystyle (r_{i-1},r_{i})}和(ri,ri+1){\displaystyle (r_{i},r_{i+1})}的最大公约数是一样的,所以最终得到的rk{\displaystyle r_{k}}是a{\displaystyle a},b{\displaystyle b}的最大公约数。

在欧几里得算法正确性的基础上,又对于a=r0{\displaystyle a=r_{0}}和b=r1{\displaystyle b=r_{1}}有等式asi+bti=ri{\displaystyle as_{i}+bt_{i}=r_{i}}成立(i = 0 或 1)。这一关系由下列递推式对所有i>1{\displaystyle i>1}成立:

ri+1=ri−1−riqi=(asi−1+bti−1)−(asi+bti)qi=(asi−1−asiqi)+(bti−1−btiqi)=asi+1+bti+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}}

因此si{\displaystyle s_{i}}和ti{\displaystyle t_{i}}满足裴蜀等式,这就证明了扩展欧几里得算法的正确性。

实现[编辑]

以下是扩展欧几里德算法的Python实现:

def ext_euclid(a, b):old_s,s=1,0old_t,t=0,1old_r,r=a,bif b == 0:return 1, 0, aelse:while(r!=0):q=old_r//rold_r,r=r,old_r-q*rold_s,s=s,old_s-q*sold_t,t=t,old_t-q*treturn old_s, old_t, old_r

扩展欧几里得算法C语言实现:

#include //這裡用了int型別,所支持的整數範圍較小,且本程序僅支持非負整數,可能缺乏實際用途,僅供展示。struct EX_GCD { //s,t是裴蜀等式中的係數,gcd是a,b的最大公因數int s;int t;int gcd;};struct EX_GCD extended_euclidean(int a, int b) {struct EX_GCD ex_gcd;if (b == 0) { //b=0時直接結束求解ex_gcd.s = 1;ex_gcd.t = 0;ex_gcd.gcd = 0;return ex_gcd;}int old_r = a, r = b;int old_s = 1, s = 0;int old_t = 0, t = 1;while (r != 0) { //按擴展歐基里德算法進行循環int q = old_r / r;int temp = old_r;old_r = r;r = temp - q * r;temp = old_s;old_s = s;s = temp - q * s;temp = old_t;old_t = t;t = temp - q * t;}ex_gcd.s = old_s;ex_gcd.t = old_t;ex_gcd.gcd = old_r;return ex_gcd;}int main(void) {int a, b;printf("Please input two integers divided by a space.\n");scanf("%d%d", &a, &b);if (a https://www.shan-machinery.com