密碼學(xué) 歐幾里得算法

Euclidean歐幾里德算法又稱輾轉(zhuǎn)相除法，是指用于計(jì)算兩個(gè)非負(fù)整數(shù)a，b的最大公約數(shù)。應(yīng)用領(lǐng)域有數(shù)學(xué)和計(jì)算機(jī)兩個(gè)方面。計(jì)算公式gcd(a,b) = gcd(b,a mod b)。

簡(jiǎn)介

歐幾里德算法是用來求兩個(gè)正整數(shù)最大公約數(shù)的算法。古希臘數(shù)學(xué)家歐幾里德在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里德算法。 擴(kuò)展歐幾里德算法可用于RSA加密等領(lǐng)域。 假如需要求 1997 和 615 兩個(gè)正整數(shù)的最大公約數(shù),用歐幾里德算法，是這樣進(jìn)行的： 1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / 5 = 1 (余2) 5 / 2 = 2 (余1) 2 / 1 = 2 (余0) 至此，最大公約數(shù)為1 以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，當(dāng)余數(shù)為 0 時(shí)，取當(dāng)前算式除數(shù)為最大公約數(shù)，所以就得出了 1997 和 615 的最大公約數(shù) 1。

算法

代碼實(shí)現(xiàn)

/*
歐幾里德算法：輾轉(zhuǎn)求余
原理： gcd(a,b)=gcd(b,a mod b)
當(dāng)b為0時(shí)，兩數(shù)的最大公約數(shù)即為a
getchar()會(huì)接受前一個(gè)scanf的回車符
*/
#include<stdio.h>
unsigned int Gcd(unsigned int M,unsigned int N)
{
    unsigned int Rem;
    while(N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}
int main(void)
{
    int a,b;
    scanf("%d %d",&a,&b);
    printf("the greatest common factor of %d and %d is ",a,b);
    printf("%d\n",Gcd(a,b));
    return 0;
}

算法拓展

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

證明：設(shè) a>b。

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

　　2，ab!=0 時(shí)

　　設(shè) ax1+by1=gcd(a,b);

　　bx2+(a mod b)y2=gcd(b,a mod b);

　　根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);

　　則:ax1+by1=bx2+(a mod b)y2;

　　即:ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)by2;

　　根據(jù)恒等定理得：x1=y2; y1=x2-(a/b)*y2; 這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

　 上面的思想是以遞歸定義的，因?yàn)?gcd 不斷的遞歸求解一定會(huì)有個(gè)時(shí)候 b=0，所以遞歸可以結(jié)束。 擴(kuò)展歐幾里德算法不但能計(jì)算(a，b）的最大公約數(shù)，而且能計(jì)算a模b及b模a的乘法逆元，用C語(yǔ)言描述如下：

#include <stdio.h>
unsigned int gcdExtended( int a,  int b,  int *x,  int *y);
int main(void) {

 
    int  a, b,GCD;
    int   x, y;

 
    a = 1232, b = 573;

 
    /*
    gcdExtended(1232, 573)時(shí), x = 20 and y = –43
    1232x + 573y = 1
    24640-24639 = 1
    或者gcdExtended( 573,1232) 時(shí),x=-43, y=20
    573x+1232y = 1
    -43*573+1232*20 = -24639+57640 = 1

 
    gcdExtended(9151, 5787) 時(shí)
    x=2011, y=-3180

 
     */
    GCD =  gcdExtended(a, b,&x, &y);
    printf("gcdExtended(%d, %d) = %d, x=%d, y=%d\n", a, b, GCD,x,y);

 
    return 0;
}

 
// 歐幾里得擴(kuò)展算法的C語(yǔ)言實(shí)現(xiàn)
// ax+by=1
unsigned int gcdExtended(int a, int b, int *x, int *y){

 
    if (a == 0){
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = gcdExtended(b%a, a, &x1, &y1);

 
    *x = y1 - (b/a) * x1;
    *y = x1;

 
    return gcd;
}