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