一、歐幾里德算法

又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a,b的最大公約數(shù)。

基本算法：設(shè)a=qb+r，其中a，b，q，r都是整數(shù)，則gcd（a,b）=gcd（b，r），即gcd（a，b）=gcd（b，a%b）

整除：

若整數(shù)a除以非零整數(shù)b，商為整數(shù)，且余數(shù)為零，我們就說a能被b整除（或說b能整除a），a為被除數(shù)，b為除數(shù)，即b|a（“|”是整除符號(hào)），讀作“b整除a”或“a能被b整除”。a叫做b的倍數(shù)，b叫做a的約數(shù)（或因數(shù)）。

證明（法一）：

若a可以表示為a=kb+r，則r=a mod b；

假設(shè)d是a，b的一個(gè)公約數(shù)，則有d|a，d|b，而r=a-kb，因此d|r，因此d是（b，a mod b）的公約數(shù)；

假設(shè)d是（b，a mod b）的公約數(shù)，則d|b，d|r，但是a=kb+r，因此d|a，所以d也是（a，b）的公約數(shù)；

因此，（a，b）和（b，a mod b）的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，即gcd（a,b）=gcd（b，r）。

證明（法二）：

假設(shè)c是a，b的最大公約數(shù)，即c=gcd（a，b），則有a=mc，b=nc，其中m，n為正整數(shù)，且m，n互為質(zhì)數(shù)；

由r=a mod b可知，r=a-qb，其中q是正整數(shù)，則r=a-qb=mc-qnc=（m-qn）c；

b=nc，r=（m-qn）c，且n，m-qn互質(zhì)

（假設(shè)n，m-qn不互質(zhì)，則n=xd，m-qn=yd，其中x，y，d都是正整數(shù)，且d>1，則a=mc=（yd+qn）c=（yd+qxd）c=（qx+y）dc，b=xdc，這時(shí)a，b的最大公約數(shù)變成dc，與前提矛盾，所以n，m-qn一定互質(zhì)）

則gcd（b，r）=c=gcd（a，b）

二、擴(kuò)展歐幾里德算法

基本算法：對(duì)于不完全為0的非負(fù)整數(shù)a，b，必存在整數(shù)對(duì)x，y，使得gcd（a，b）=ax+by。

證明：

設(shè)a>b

1、當(dāng)b=0時(shí)，gcd（a，b）=a。此時(shí)x=1，y=0;

2、ab！=0時(shí)，設(shè)

? ? ?a x1+b y1=gcd（a，b）；b x2+（a mod b） y2=gcd（b，a mod b）；

? ? ?根據(jù)樸素的歐幾里德原理有g(shù)cd（a，b）=gcd（b，a mod b）；

? ? ?則：a x1+b y1 =b x2+（a mod b）y2；

? ? ?即：a x1+b y1 =b x2+（a-（a/b）*b）y2=a y2+b x2-（a/b）+b y2；

? ? ?根據(jù)恒定定理得：x1=y2，y1=x2-（a/b）* y2；

? ? ?這樣我們就得到了求解x1，y1的方法：x1，y1的值基于x2，y2。

? ? ?上面的思想是以遞歸定義的，因?yàn)間cd不斷的遞歸求解一定會(huì)有個(gè)時(shí)候b=0，所以遞歸可以結(jié)束。

總結(jié)

以上是生活随笔為你收集整理的欧几里德与扩展欧几里德算法——密码学笔记（五）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。