1 /* @(#)gcd.c 4.1 12/25/82 */ 2 3 #include <mp.h> 4 gcd(a,b,c) MINT *a,*b,*c; 5 { MINT x,y,z,w; 6 x.len=y.len=z.len=w.len=0; 7 move(a,&x); 8 move(b,&y); 9 while(y.len!=0) 10 { mdiv(&x,&y,&w,&z); 11 move(&y,&x); 12 move(&z,&y); 13 } 14 move(&x,c); 15 xfree(&x); 16 xfree(&y); 17 xfree(&z); 18 xfree(&w); 19 return; 20 } 21 invert(a, b, c) MINT *a, *b, *c; 22 { MINT x, y, z, w, Anew, Aold; 23 int i = 0; 24 x.len = y.len = z.len = w.len = Aold.len = 0; 25 Anew.len = 1; 26 Anew.val = xalloc(1); 27 *Anew.val = 1; 28 move(b, &x); 29 move(a, &y); 30 while(y.len != 0) 31 { mdiv(&x, &y, &w, &z); 32 move(&Anew, &x); 33 mult(&w, &Anew, &Anew); 34 madd(&Anew, &Aold, &Anew); 35 move(&x, &Aold); 36 move(&y, &x); 37 move(&z, &y); 38 i++; 39 } 40 move(&Aold, c); 41 if( (i&01) == 0) msub(b, c, c); 42 xfree(&x); 43 xfree(&y); 44 xfree(&z); 45 xfree(&w); 46 xfree(&Aold); 47 xfree(&Anew); 48 } 49