148370Sbostic /*-
248370Sbostic * %sccs.include.proprietary.c%
348370Sbostic */
448370Sbostic
519819Sdist #ifndef lint
6*61321Sbostic static char sccsid[] = "@(#)gcd.c 8.1 (Berkeley) 06/04/93";
748370Sbostic #endif /* not lint */
819819Sdist
99944Ssam #include <mp.h>
gcd(a,b,c)109944Ssam gcd(a,b,c) MINT *a,*b,*c;
119944Ssam { MINT x,y,z,w;
129944Ssam x.len=y.len=z.len=w.len=0;
139944Ssam move(a,&x);
149944Ssam move(b,&y);
159944Ssam while(y.len!=0)
169944Ssam { mdiv(&x,&y,&w,&z);
179944Ssam move(&y,&x);
189944Ssam move(&z,&y);
199944Ssam }
209944Ssam move(&x,c);
219944Ssam xfree(&x);
229944Ssam xfree(&y);
239944Ssam xfree(&z);
249944Ssam xfree(&w);
259944Ssam return;
269944Ssam }
invert(a,b,c)279944Ssam invert(a, b, c) MINT *a, *b, *c;
289944Ssam { MINT x, y, z, w, Anew, Aold;
299944Ssam int i = 0;
309944Ssam x.len = y.len = z.len = w.len = Aold.len = 0;
319944Ssam Anew.len = 1;
3226858Sdonn Anew.val = xalloc(1, "invert");
339944Ssam *Anew.val = 1;
349944Ssam move(b, &x);
359944Ssam move(a, &y);
369944Ssam while(y.len != 0)
379944Ssam { mdiv(&x, &y, &w, &z);
389944Ssam move(&Anew, &x);
399944Ssam mult(&w, &Anew, &Anew);
409944Ssam madd(&Anew, &Aold, &Anew);
419944Ssam move(&x, &Aold);
429944Ssam move(&y, &x);
439944Ssam move(&z, &y);
449944Ssam i++;
459944Ssam }
469944Ssam move(&Aold, c);
479944Ssam if( (i&01) == 0) msub(b, c, c);
489944Ssam xfree(&x);
499944Ssam xfree(&y);
509944Ssam xfree(&z);
519944Ssam xfree(&w);
529944Ssam xfree(&Aold);
539944Ssam xfree(&Anew);
549944Ssam }
55