Mercurial > dropbear

comparison libtommath/bn_mp_invmod_slow.c @ 1436:60fc6476e044

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update to libtommath v1.0
author Matt Johnston <matt@ucc.asn.au>
date Sat, 24 Jun 2017 22:37:14 +0800
parents 5ff8218bcee9
children 8bba51a55704
comparison
equal deleted inserted replaced
1435:f849a5ca2efc 1436:60fc6476e044
1 #include <tommath.h> 1 #include <tommath_private.h>
2 #ifdef BN_MP_INVMOD_SLOW_C 2 #ifdef BN_MP_INVMOD_SLOW_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 * 4 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
13 * guarantee it works. 13 * guarantee it works.
14 * 14 *
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com 15 * Tom St Denis, [email protected], http://libtom.org
16 */ 16 */
17 17
18 /* hac 14.61, pp608 */ 18 /* hac 14.61, pp608 */
19 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c) 19 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c)
20 { 20 {
21 mp_int x, y, u, v, A, B, C, D; 21 mp_int x, y, u, v, A, B, C, D;
22 int res; 22 int res;
23 23
24 /* b cannot be negative */ 24 /* b cannot be negative */
25 if (b->sign == MP_NEG || mp_iszero(b) == 1) { 25 if ((b->sign == MP_NEG) || (mp_iszero(b) == MP_YES)) {
26 return MP_VAL; 26 return MP_VAL;
27 } 27 }
28 28
29 /* init temps */ 29 /* init temps */
30 if ((res = mp_init_multi(&x, &y, &u, &v, 30 if ((res = mp_init_multi(&x, &y, &u, &v,
39 if ((res = mp_copy (b, &y)) != MP_OKAY) { 39 if ((res = mp_copy (b, &y)) != MP_OKAY) {
40 goto LBL_ERR; 40 goto LBL_ERR;
41 } 41 }
42 42
43 /* 2. [modified] if x,y are both even then return an error! */ 43 /* 2. [modified] if x,y are both even then return an error! */
44 if (mp_iseven (&x) == 1 && mp_iseven (&y) == 1) { 44 if ((mp_iseven (&x) == MP_YES) && (mp_iseven (&y) == MP_YES)) {
45 res = MP_VAL; 45 res = MP_VAL;
46 goto LBL_ERR; 46 goto LBL_ERR;
47 } 47 }
48 48
49 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */ 49 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
56 mp_set (&A, 1); 56 mp_set (&A, 1);
57 mp_set (&D, 1); 57 mp_set (&D, 1);
58 58
59 top: 59 top:
60 /* 4. while u is even do */ 60 /* 4. while u is even do */
61 while (mp_iseven (&u) == 1) { 61 while (mp_iseven (&u) == MP_YES) {
62 /* 4.1 u = u/2 */ 62 /* 4.1 u = u/2 */
63 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) { 63 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
64 goto LBL_ERR; 64 goto LBL_ERR;
65 } 65 }
66 /* 4.2 if A or B is odd then */ 66 /* 4.2 if A or B is odd then */
67 if (mp_isodd (&A) == 1 || mp_isodd (&B) == 1) { 67 if ((mp_isodd (&A) == MP_YES) || (mp_isodd (&B) == MP_YES)) {
68 /* A = (A+y)/2, B = (B-x)/2 */ 68 /* A = (A+y)/2, B = (B-x)/2 */
69 if ((res = mp_add (&A, &y, &A)) != MP_OKAY) { 69 if ((res = mp_add (&A, &y, &A)) != MP_OKAY) {
70 goto LBL_ERR; 70 goto LBL_ERR;
71 } 71 }
72 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) { 72 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
81 goto LBL_ERR; 81 goto LBL_ERR;
82 } 82 }
83 } 83 }
84 84
85 /* 5. while v is even do */ 85 /* 5. while v is even do */
86 while (mp_iseven (&v) == 1) { 86 while (mp_iseven (&v) == MP_YES) {
87 /* 5.1 v = v/2 */ 87 /* 5.1 v = v/2 */
88 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) { 88 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
89 goto LBL_ERR; 89 goto LBL_ERR;
90 } 90 }
91 /* 5.2 if C or D is odd then */ 91 /* 5.2 if C or D is odd then */
92 if (mp_isodd (&C) == 1 || mp_isodd (&D) == 1) { 92 if ((mp_isodd (&C) == MP_YES) || (mp_isodd (&D) == MP_YES)) {
93 /* C = (C+y)/2, D = (D-x)/2 */ 93 /* C = (C+y)/2, D = (D-x)/2 */
94 if ((res = mp_add (&C, &y, &C)) != MP_OKAY) { 94 if ((res = mp_add (&C, &y, &C)) != MP_OKAY) {
95 goto LBL_ERR; 95 goto LBL_ERR;
96 } 96 }
97 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) { 97 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
135 goto LBL_ERR; 135 goto LBL_ERR;
136 } 136 }
137 } 137 }
138 138
139 /* if not zero goto step 4 */ 139 /* if not zero goto step 4 */
140 if (mp_iszero (&u) == 0) 140 if (mp_iszero (&u) == MP_NO)
141 goto top; 141 goto top;
142 142
143 /* now a = C, b = D, gcd == g*v */ 143 /* now a = C, b = D, gcd == g*v */
144 144
145 /* if v != 1 then there is no inverse */ 145 /* if v != 1 then there is no inverse */
168 LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL); 168 LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
169 return res; 169 return res;
170 } 170 }
171 #endif 171 #endif
172 172
173 /* $Source: /cvs/libtom/libtommath/bn_mp_invmod_slow.c,v $ */ 173 /* $Source$ */
174 /* $Revision: 1.3 $ */ 174 /* $Revision$ */
175 /* $Date: 2006/03/31 14:18:44 $ */ 175 /* $Date$ */