1 /*- 2 * %sccs.include.proprietary.c% 3 */ 4 5 #ifndef lint 6 static char sccsid[] = "@(#)gcd.c 8.1 (Berkeley) 06/04/93"; 7 #endif /* not lint */ 8 9 #include <mp.h> 10 gcd(a,b,c) MINT *a,*b,*c; 11 { MINT x,y,z,w; 12 x.len=y.len=z.len=w.len=0; 13 move(a,&x); 14 move(b,&y); 15 while(y.len!=0) 16 { mdiv(&x,&y,&w,&z); 17 move(&y,&x); 18 move(&z,&y); 19 } 20 move(&x,c); 21 xfree(&x); 22 xfree(&y); 23 xfree(&z); 24 xfree(&w); 25 return; 26 } 27 invert(a, b, c) MINT *a, *b, *c; 28 { MINT x, y, z, w, Anew, Aold; 29 int i = 0; 30 x.len = y.len = z.len = w.len = Aold.len = 0; 31 Anew.len = 1; 32 Anew.val = xalloc(1, "invert"); 33 *Anew.val = 1; 34 move(b, &x); 35 move(a, &y); 36 while(y.len != 0) 37 { mdiv(&x, &y, &w, &z); 38 move(&Anew, &x); 39 mult(&w, &Anew, &Anew); 40 madd(&Anew, &Aold, &Anew); 41 move(&x, &Aold); 42 move(&y, &x); 43 move(&z, &y); 44 i++; 45 } 46 move(&Aold, c); 47 if( (i&01) == 0) msub(b, c, c); 48 xfree(&x); 49 xfree(&y); 50 xfree(&z); 51 xfree(&w); 52 xfree(&Aold); 53 xfree(&Anew); 54 } 55