annotate bn_mp_invmod_slow.c @ 386:97db060d0ef5 libtommath-orig libtommath-0.40

Update to LibTomMath 0.40
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 03:11:15 +0000
parents 91fbc376f010
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
282
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 #include <tommath.h>
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 #ifdef BN_MP_INVMOD_SLOW_C
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 *
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 * LibTomMath is a library that provides multiple-precision
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * integer arithmetic as well as number theoretic functionality.
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 *
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * The library was designed directly after the MPI library by
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 * Michael Fromberger but has been written from scratch with
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * additional optimizations in place.
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 *
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 * The library is free for all purposes without any express
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 * guarantee it works.
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 *
386
97db060d0ef5 Update to LibTomMath 0.40
Matt Johnston <matt@ucc.asn.au>
parents: 282
diff changeset
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com
282
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 /* hac 14.61, pp608 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c)
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 mp_int x, y, u, v, A, B, C, D;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 int res;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 /* b cannot be negative */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 if (b->sign == MP_NEG || mp_iszero(b) == 1) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 return MP_VAL;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 /* init temps */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 if ((res = mp_init_multi(&x, &y, &u, &v,
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 &A, &B, &C, &D, NULL)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 return res;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 /* x = a, y = b */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 if ((res = mp_mod(a, b, &x)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 if ((res = mp_copy (b, &y)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 /* 2. [modified] if x,y are both even then return an error! */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 if (mp_iseven (&x) == 1 && mp_iseven (&y) == 1) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 res = MP_VAL;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 if ((res = mp_copy (&x, &u)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 if ((res = mp_copy (&y, &v)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 mp_set (&A, 1);
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 mp_set (&D, 1);
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 top:
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 /* 4. while u is even do */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61 while (mp_iseven (&u) == 1) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 /* 4.1 u = u/2 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 /* 4.2 if A or B is odd then */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 if (mp_isodd (&A) == 1 || mp_isodd (&B) == 1) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 /* A = (A+y)/2, B = (B-x)/2 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 if ((res = mp_add (&A, &y, &A)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 /* A = A/2, B = B/2 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 if ((res = mp_div_2 (&A, &A)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 /* 5. while v is even do */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 while (mp_iseven (&v) == 1) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 /* 5.1 v = v/2 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
89 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
90 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
91 /* 5.2 if C or D is odd then */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
92 if (mp_isodd (&C) == 1 || mp_isodd (&D) == 1) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93 /* C = (C+y)/2, D = (D-x)/2 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 if ((res = mp_add (&C, &y, &C)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
95 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
97 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
98 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
100 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
101 /* C = C/2, D = D/2 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
102 if ((res = mp_div_2 (&C, &C)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
103 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
104 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
105 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
106 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
107 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
108 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
109
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
110 /* 6. if u >= v then */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
111 if (mp_cmp (&u, &v) != MP_LT) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
112 /* u = u - v, A = A - C, B = B - D */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
113 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
114 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
115 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
116
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
117 if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
118 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
119 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
120
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
123 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
124 } else {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125 /* v - v - u, C = C - A, D = D - B */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
128 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
129
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
130 if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
131 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
132 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
133
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
134 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
135 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
136 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
137 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
138
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
139 /* if not zero goto step 4 */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
140 if (mp_iszero (&u) == 0)
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
141 goto top;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
142
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
143 /* now a = C, b = D, gcd == g*v */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
144
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
145 /* if v != 1 then there is no inverse */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
146 if (mp_cmp_d (&v, 1) != MP_EQ) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
147 res = MP_VAL;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
148 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
149 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
150
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
151 /* if its too low */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
152 while (mp_cmp_d(&C, 0) == MP_LT) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
153 if ((res = mp_add(&C, b, &C)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
154 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
155 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
156 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
157
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
158 /* too big */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
159 while (mp_cmp_mag(&C, b) != MP_LT) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
160 if ((res = mp_sub(&C, b, &C)) != MP_OKAY) {
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
161 goto LBL_ERR;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
162 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
163 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
164
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
165 /* C is now the inverse */
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
166 mp_exch (&C, c);
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
167 res = MP_OKAY;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
168 LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
169 return res;
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
170 }
91fbc376f010 Import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
171 #endif
386
97db060d0ef5 Update to LibTomMath 0.40
Matt Johnston <matt@ucc.asn.au>
parents: 282
diff changeset
172
97db060d0ef5 Update to LibTomMath 0.40
Matt Johnston <matt@ucc.asn.au>
parents: 282
diff changeset
173 /* $Source: /cvs/libtom/libtommath/bn_mp_invmod_slow.c,v $ */
97db060d0ef5 Update to LibTomMath 0.40
Matt Johnston <matt@ucc.asn.au>
parents: 282
diff changeset
174 /* $Revision: 1.3 $ */
97db060d0ef5 Update to LibTomMath 0.40
Matt Johnston <matt@ucc.asn.au>
parents: 282
diff changeset
175 /* $Date: 2006/03/31 14:18:44 $ */