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>
gcd(a,b,c)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 }
invert(a,b,c)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