《扩展欧几里得算法描述.doc》由会员分享，可在线阅读，更多相关《扩展欧几里得算法描述.doc（5页珍藏版）》请在金锄头文库上搜索。
1、扩展欧几里得算法：欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如：gcd (26, 15)26 % 15 = 1 . 1115 % 11 = 1 . 411 % 4 = 2 . 34 % 3 = 1 . 13 % 1 = 3 . 0 可知，gcd (26, 15) = 1如果 gcd(x, y) = r，那么有 ax + by = r，可以看出，上面的步骤实际上是可以直接得出 a, b 的：null26 % 15 = 1 . 11 = 11 = 26 - 15 1 1 -115 % 11 = 1 . 4 = 4 = 15 - 11 = 15 - (26 - 15) = -2
2、6 + 2*15 1 -1 211 % 4 = 2 . 3 = 3 = 11 - 4*2 = (26 - 15) - (-26 + 15) * 2 = 3*26 - 5*15 2 3 -54 % 3 = 1 . 1 = 1 = 4 - 3 = (-26 + 2*15) - (3*26 - 5*15) = -4*26 + 7*15 1 -4 73 % 1 = 3 . 0 在每一轮，我们都可以得到一个模的表达式为：ri = aix + biy如果不考虑第一轮和第二轮，那么ai 和 bi 可以表示为(qi 为每一轮得到的商)：ai = ai-2 - qi * ai-1bi = bi-2 - qi *
3、 bi-1证明如下：输入：x,y,则有如下：x/y=q1.r1 =r1=x-q1*yy/r1=q2r2 =r2=y-q2*r1=y-q2*(x-q1*y)=-q2*x+(1+q2*q1)*yr1/r2=q3r3 =r3=r1-q3*r2=(x-q1*y)-q3*(-q2*x+(1+q2*q1)*y)=(1+q2*q3)x+(-q1-q3*(1+q2*q3)*y则可以看出有：a3=1+q3*q2=a1-q3*a2B3=b1-q3*b2由此可以推测出：ai = ai-2 - qi * ai-1bi = bi-2 - qi * bi-1但是a1,b1,a2,b2比较特别：a1=1=a-1 q1*a0
4、b1=-q1=b-1 q1*b0由此我们可以知道a-1=1,a0=0,b-1=0,b0=1即可满足。所以这个是初试条件。现在来考虑第一轮和第二轮，按照上面的公式，可以认为a-1 = 1, b-1 = 0a0 = 0, b0 = 1有了这两对预设值，上面的两个公式就成立了求逆元，由上面可以看出，gcd(x, y) = 1 的时候如果 ax + by = 1，那么 ax = -by + 1 = ax = 1 (mod b)这时候，a 即是 x 的逆元1 #include 23 int gcd (int x, int y, int *a1, int *a2, int *b1, int *b2)4 5
5、 int q, r, a, b;67 q = x / y;8 r = x % y;910 a = *a2 - q*(*a1);11 b = *b2 - q*(*b1);1213 if (0 = r)14 15 return y;16 1718 *a2 = *a1;19 *b2 = *b1;2021 *a1 = a;22 *b1 = b;2324 return gcd (y, r, a1, a2, b1, b2);25 2627 int main (int argc, char *argv)28 29 int x, y, a1, a2, b1, b2, r;3031 x = atoi (argv1);32 y = atoi (argv2);3334 a1 = 0;35 a2 = 1;36 b1 = 1;37 b2 = 0;3839 r = gcd (x, y, &a1, &a2, &b1, &b2);4041 printf (%d = (%d) * (%d) + (%d) * (%d)n,42 r, a1, x, b1, y);4344 return 0;45
