扩展的欧几里得算法(Extended Euclidean algorithm)

扩展的欧几里得算法是欧几里得算法的扩展，除了计算a，b两个数的最大公因数，还能找到整数x,y，
使得ax + by = d = gcd(a, b)。它对于有限域中的计算以及RSA等密码算法非常重要。
github源码

推理（推理过程与上一章类似）：
设：
$a = q_{1}b + r_{1} , r_{1} = ax_{1} + by_{1}$
$b = q_{2}r_{1} + r_{2} , r_{2} = ax_{2} + by_{2}$
$r_{1} = q_{3}r_{2} + r_{3} , r_{3} = ax_{3} + by_{3}%$
…
$r_{i-2} = q_{i}r_{i-1} + r_{i} , r_{i} = ax_{i} + by_{i}$
…
$r_{n-2} = q_{n}r_{n-1} + r_{n} , r_{n} = ax_{n} + by_{n}$
$r_{n-1} = q_{n+1}r_{n} + 0$

则：
$r_{i} = r_{i-2} -q_{i}r_{i-1}$
因：
$r_{i-2} = ax_{i-2} + by_{i-2}$
$r_{i-1} = ax_{i-1} + by_{i-1}$
$r_{i} = ax_{i} + by_{i}$
代入，得：
$ax_{i} + by_{i} = (ax_{i-2} + by_{i-2}) - q_{i}(ax_{i-1} + by_{i-1})$
$= a(x_{i-2} - q_{i}x_{i-1}) + b(y_{i-2} -q_{i}y_{i-1})$
即：
$x_{i} = x_{i-2} - q_{i}x_{i-1}$
$y_{i} = y_{i-2} - q_{i}y_{i-1}$

由$r_{i} = r_{i-2} -q_{i}r_{i-1}$可知，
新余数$r_{i}$的计算基于前面两个计算的余数$r_{i-1}$和$r_{i-2}$，
那么若按此方式计算，在开始时需要知道$r_{0}$和$r_{-1}$的值，令$r_{-1}=a$，$r_{0} = b$,则有：

计算 满足 计算 满足
$r_{-1}=a$ $x_{-1}=1$
$y_{-1}=0$		 $a=ax_{-1}+by_{-1}$
$r_{0}=b$ $x_{0}=0$
$y_{0}=1$		 $b=ax_{0}+by_{0}$
$r_{1}$ = a mod b
$q_{1} = a / b$		 $a = q_{1}b+r_{1}$ $x_{1}=x_{-1}-q_{1}x_{0}=1$
$y_{1}=y_{-1}-q_{1}y_{0}=-q_{1}$		 $r_{1}=ax_{1}+by_{1}$
$r_{2}$ = b mod $r_{1}$
$q_{2} = b / r_{1}$		 $b = q_{2}r_{1}+r_{2}$ $x_{2}=x_{0}-q_{2}x_{1}$
$y_{2}=y_{0}-q_{2}y_{1}$		 $r_{2}=ax_{2}+by_{2}$
$r_{3} = r_{1}$ mod $r_{2}$
$q_{3} = r_{1} / r_{2}$		 $r_{1} = q_{3}r_{2}+r_{3}$ $x_{3}=x_{1}-q_{3}x_{2}$
$y_{3}=y_{1}-q_{3}y_{2}$		 $r_{3}=ax_{3}+by_{3}$
… … … …
$r_{n} = r_{n-2}$ mod $r_{n-1}$
$q_{n} = r_{n-2} / r_{n-1}$		 $r_{n-2} = q_{n}r_{n-1}+r_{n}$ $x_{n}=x_{n-2}-q_{n}x_{n-1}$
$y_{n}=y_{n-2}-q_{n}y_{n-1}$		 $r_{n}=ax_{n}+by_{n}$
$r_{n+1} = r_{n-1}$ mod $r_{n} = 0$
$q_{n+1} = r_{n-1} / r_{n}$		 $r_{n-1} = q_{n+1}r_{n} + 0$ $d=gcd(a, b)=r_{n}$
$x = x_{n};y = y_{n}$

C实现

循环方式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// Extended Euclidean Algorithm
// d = gcd(a, b) = ax + by
// input a,b
// output x,y
// return d
int gcd_ex(int a, int b, int *x, int *y){
    int a_temp;
    int b_temp;

    int a_negative_flag = 0;
    int b_negative_flag = 0;
    int a_b_swap_flag = 0;

    int x1 = 1; //init value
    int y1 = 0; //x(-1) = 1, y(-1) = 0;
    int x2 = 0;
    int y2 = 1; //x(0) = 0, y(0) = 1;

    int q; // q = a_temp / b_temp;
    int r; // r = a_temp % b_temp;

    if(a < 0){
        a_temp = -a;
        a_negative_flag = 1;
    }else{
        a_temp = a;
    }

    if(b < 0){
        b_temp = -b;
        b_negative_flag = 1;
    }else{
        b_temp = b;
    }

    if(b_temp > a_temp){
        r = a_temp;
        a_temp = b_temp;
        b_temp = r;
        a_b_swap_flag = 1;
    }

    if(b_temp == 0){
        *x = 1;
        *y = 0;
        if(a_b_swap_flag){
            *x = 0;
            *y = 1;
        }
        if(a_negative_flag){
            *x = -*x;
        }
        if(b_negative_flag){
            *y = -*y;
        }
        return a_temp;
    }

    r = a_temp % b_temp;
    q = a_temp / b_temp;

    if(r == 0){
        *x = 0;
        *y = 1;
        if(a_b_swap_flag){
            *x = 1;
            *y = 0;
        }
        if(a_negative_flag){
            *x = -*x;
        }
        if(b_negative_flag){
            *y = -*y;
        }
        return b_temp;
    }

    while(r != 0){
        *x = x1 - (q * x2);
        *y = y1 - (q * y2);
        x1 = x2;
        y1 = y2;
        x2 = *x;
        y2 = *y;
        a_temp = b_temp;
        b_temp = r;
        r = a_temp % b_temp;
        q = a_temp / b_temp;
    }

    if(a_b_swap_flag){
        r = *x;
        *x = *y;
        *y = r;
    }
    if(a_negative_flag){
        *x = -*x;
    }
    if(b_negative_flag){
        *y = -*y;
    }

    return b_temp;