1*7c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
2*7c478bd9Sstevel@tonic-gate /* All Rights Reserved */
3*7c478bd9Sstevel@tonic-gate
4*7c478bd9Sstevel@tonic-gate
5*7c478bd9Sstevel@tonic-gate /*
6*7c478bd9Sstevel@tonic-gate * Copyright (c) 1980 Regents of the University of California.
7*7c478bd9Sstevel@tonic-gate * All rights reserved. The Berkeley software License Agreement
8*7c478bd9Sstevel@tonic-gate * specifies the terms and conditions for redistribution.
9*7c478bd9Sstevel@tonic-gate */
10*7c478bd9Sstevel@tonic-gate /* Portions Copyright(c) 1988, Sun Microsystems Inc. */
11*7c478bd9Sstevel@tonic-gate /* All Rights Reserved */
12*7c478bd9Sstevel@tonic-gate
13*7c478bd9Sstevel@tonic-gate /*
14*7c478bd9Sstevel@tonic-gate * Copyright (c) 1997, by Sun Microsystems, Inc.
15*7c478bd9Sstevel@tonic-gate * All rights reserved.
16*7c478bd9Sstevel@tonic-gate */
17*7c478bd9Sstevel@tonic-gate
18*7c478bd9Sstevel@tonic-gate #ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.1 */
19*7c478bd9Sstevel@tonic-gate
20*7c478bd9Sstevel@tonic-gate /* LINTLIBRARY */
21*7c478bd9Sstevel@tonic-gate
22*7c478bd9Sstevel@tonic-gate #include <mp.h>
23*7c478bd9Sstevel@tonic-gate #include "libmp.h"
24*7c478bd9Sstevel@tonic-gate #include <sys/types.h>
25*7c478bd9Sstevel@tonic-gate
26*7c478bd9Sstevel@tonic-gate void
mp_gcd(MINT * a,MINT * b,MINT * c)27*7c478bd9Sstevel@tonic-gate mp_gcd(MINT *a, MINT *b, MINT *c)
28*7c478bd9Sstevel@tonic-gate {
29*7c478bd9Sstevel@tonic-gate MINT x, y, z, w;
30*7c478bd9Sstevel@tonic-gate
31*7c478bd9Sstevel@tonic-gate x.len = y.len = z.len = w.len = 0;
32*7c478bd9Sstevel@tonic-gate _mp_move(a, &x);
33*7c478bd9Sstevel@tonic-gate _mp_move(b, &y);
34*7c478bd9Sstevel@tonic-gate while (y.len != 0) {
35*7c478bd9Sstevel@tonic-gate mp_mdiv(&x, &y, &w, &z);
36*7c478bd9Sstevel@tonic-gate _mp_move(&y, &x);
37*7c478bd9Sstevel@tonic-gate _mp_move(&z, &y);
38*7c478bd9Sstevel@tonic-gate }
39*7c478bd9Sstevel@tonic-gate _mp_move(&x, c);
40*7c478bd9Sstevel@tonic-gate _mp_xfree(&x);
41*7c478bd9Sstevel@tonic-gate _mp_xfree(&y);
42*7c478bd9Sstevel@tonic-gate _mp_xfree(&z);
43*7c478bd9Sstevel@tonic-gate _mp_xfree(&w);
44*7c478bd9Sstevel@tonic-gate }
45*7c478bd9Sstevel@tonic-gate
46*7c478bd9Sstevel@tonic-gate void
mp_invert(MINT * x1,MINT * x0,MINT * c)47*7c478bd9Sstevel@tonic-gate mp_invert(MINT *x1, MINT *x0, MINT *c)
48*7c478bd9Sstevel@tonic-gate {
49*7c478bd9Sstevel@tonic-gate MINT u2, u3;
50*7c478bd9Sstevel@tonic-gate MINT v2, v3;
51*7c478bd9Sstevel@tonic-gate MINT zero;
52*7c478bd9Sstevel@tonic-gate MINT q, r;
53*7c478bd9Sstevel@tonic-gate MINT t;
54*7c478bd9Sstevel@tonic-gate MINT x0_prime;
55*7c478bd9Sstevel@tonic-gate static MINT *one = NULL;
56*7c478bd9Sstevel@tonic-gate
57*7c478bd9Sstevel@tonic-gate /*
58*7c478bd9Sstevel@tonic-gate * Minimize calls to allocators. Don't use pointers for local
59*7c478bd9Sstevel@tonic-gate * variables, for the one "initialized" multiple precision
60*7c478bd9Sstevel@tonic-gate * variable, do it just once.
61*7c478bd9Sstevel@tonic-gate */
62*7c478bd9Sstevel@tonic-gate if (one == NULL)
63*7c478bd9Sstevel@tonic-gate one = mp_itom(1);
64*7c478bd9Sstevel@tonic-gate
65*7c478bd9Sstevel@tonic-gate zero.len = q.len = r.len = t.len = 0;
66*7c478bd9Sstevel@tonic-gate
67*7c478bd9Sstevel@tonic-gate x0_prime.len = u2.len = u3.len = 0;
68*7c478bd9Sstevel@tonic-gate _mp_move(x0, &u3);
69*7c478bd9Sstevel@tonic-gate _mp_move(x0, &x0_prime);
70*7c478bd9Sstevel@tonic-gate
71*7c478bd9Sstevel@tonic-gate v2.len = v3.len = 0;
72*7c478bd9Sstevel@tonic-gate _mp_move(one, &v2);
73*7c478bd9Sstevel@tonic-gate _mp_move(x1, &v3);
74*7c478bd9Sstevel@tonic-gate
75*7c478bd9Sstevel@tonic-gate while (mp_mcmp(&v3, &zero) != 0) {
76*7c478bd9Sstevel@tonic-gate /* invariant: x0*u1 + x1*u2 = u3 */
77*7c478bd9Sstevel@tonic-gate /* invariant: x0*v1 + x2*v2 = v3 */
78*7c478bd9Sstevel@tonic-gate /* invariant: x(n+1) = x(n-1) % x(n) */
79*7c478bd9Sstevel@tonic-gate mp_mdiv(&u3, &v3, &q, &r);
80*7c478bd9Sstevel@tonic-gate _mp_move(&v3, &u3);
81*7c478bd9Sstevel@tonic-gate _mp_move(&r, &v3);
82*7c478bd9Sstevel@tonic-gate
83*7c478bd9Sstevel@tonic-gate mp_mult(&q, &v2, &t);
84*7c478bd9Sstevel@tonic-gate mp_msub(&u2, &t, &t);
85*7c478bd9Sstevel@tonic-gate _mp_move(&v2, &u2);
86*7c478bd9Sstevel@tonic-gate _mp_move(&t, &v2);
87*7c478bd9Sstevel@tonic-gate }
88*7c478bd9Sstevel@tonic-gate /* now x0*u1 + x1*u2 == 1, therefore, (u2*x1) % x0 == 1 */
89*7c478bd9Sstevel@tonic-gate _mp_move(&u2, c);
90*7c478bd9Sstevel@tonic-gate if (mp_mcmp(c, &zero) < 0) {
91*7c478bd9Sstevel@tonic-gate mp_madd(&x0_prime, c, c);
92*7c478bd9Sstevel@tonic-gate }
93*7c478bd9Sstevel@tonic-gate _mp_xfree(&zero);
94*7c478bd9Sstevel@tonic-gate _mp_xfree(&v2);
95*7c478bd9Sstevel@tonic-gate _mp_xfree(&v3);
96*7c478bd9Sstevel@tonic-gate _mp_xfree(&u2);
97*7c478bd9Sstevel@tonic-gate _mp_xfree(&u3);
98*7c478bd9Sstevel@tonic-gate _mp_xfree(&q);
99*7c478bd9Sstevel@tonic-gate _mp_xfree(&r);
100*7c478bd9Sstevel@tonic-gate _mp_xfree(&t);
101*7c478bd9Sstevel@tonic-gate }
102