密碼學 歐幾里得算法

Euclidean歐幾里德算法又稱輾轉相除法，是指用于計算兩個非負整數a，b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。

簡介

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

算法

代碼實現

/*
歐幾里德算法：輾轉求余
原理： gcd(a,b)=gcd(b,a mod b)
當b為0時，兩數的最大公約數即為a
getchar()會接受前一個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;
}

算法拓展

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

證明：設 a>b。

　　1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；

　　2，ab!=0 時

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

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

　　根據樸素的歐幾里德原理有 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;

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

　 上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以結束。 擴展歐幾里德算法不但能計算(a，b）的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：

#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)時, x = 20 and y = –43
    1232x + 573y = 1
    24640-24639 = 1
    或者gcdExtended( 573,1232) 時,x=-43, y=20
    573x+1232y = 1
    -43*573+1232*20 = -24639+57640 = 1

 
    gcdExtended(9151, 5787) 時
    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;
}

 
// 歐幾里得擴展算法的C語言實現
// 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;
}