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