Mercurial > dropbear

comparison bn_fast_mp_invmod.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import of libtommath 0.35
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 08:59:30 +0000
parents d29b64170cf0
children
comparison
equal deleted inserted replaced
142:d29b64170cf0 190:d8254fc979e9
19 * that is c = 1/a mod b 19 * that is c = 1/a mod b
20 * 20 *
21 * Based on slow invmod except this is optimized for the case where b is 21 * Based on slow invmod except this is optimized for the case where b is
22 * odd as per HAC Note 14.64 on pp. 610 22 * odd as per HAC Note 14.64 on pp. 610
23 */ 23 */
24 int 24 int fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
25 fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
26 { 25 {
27 mp_int x, y, u, v, B, D; 26 mp_int x, y, u, v, B, D;
28 int res, neg; 27 int res, neg;
29 28
30 /* 2. [modified] b must be odd */ 29 /* 2. [modified] b must be odd */
37 return res; 36 return res;
38 } 37 }
39 38
40 /* x == modulus, y == value to invert */ 39 /* x == modulus, y == value to invert */
41 if ((res = mp_copy (b, &x)) != MP_OKAY) { 40 if ((res = mp_copy (b, &x)) != MP_OKAY) {
42 goto __ERR; 41 goto LBL_ERR;
43 } 42 }
44 43
45 /* we need y = |a| */ 44 /* we need y = |a| */
46 if ((res = mp_abs (a, &y)) != MP_OKAY) { 45 if ((res = mp_mod (a, b, &y)) != MP_OKAY) {
47 goto __ERR; 46 goto LBL_ERR;
48 } 47 }
49 48
50 /* 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 */
51 if ((res = mp_copy (&x, &u)) != MP_OKAY) { 50 if ((res = mp_copy (&x, &u)) != MP_OKAY) {
52 goto __ERR; 51 goto LBL_ERR;
53 } 52 }
54 if ((res = mp_copy (&y, &v)) != MP_OKAY) { 53 if ((res = mp_copy (&y, &v)) != MP_OKAY) {
55 goto __ERR; 54 goto LBL_ERR;
56 } 55 }
57 mp_set (&D, 1); 56 mp_set (&D, 1);
58 57
59 top: 58 top:
60 /* 4. while u is even do */ 59 /* 4. while u is even do */
61 while (mp_iseven (&u) == 1) { 60 while (mp_iseven (&u) == 1) {
62 /* 4.1 u = u/2 */ 61 /* 4.1 u = u/2 */
63 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) { 62 if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
64 goto __ERR; 63 goto LBL_ERR;
65 } 64 }
66 /* 4.2 if B is odd then */ 65 /* 4.2 if B is odd then */
67 if (mp_isodd (&B) == 1) { 66 if (mp_isodd (&B) == 1) {
68 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) { 67 if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
69 goto __ERR; 68 goto LBL_ERR;
70 } 69 }
71 } 70 }
72 /* B = B/2 */ 71 /* B = B/2 */
73 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) { 72 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
74 goto __ERR; 73 goto LBL_ERR;
75 } 74 }
76 } 75 }
77 76
78 /* 5. while v is even do */ 77 /* 5. while v is even do */
79 while (mp_iseven (&v) == 1) { 78 while (mp_iseven (&v) == 1) {
80 /* 5.1 v = v/2 */ 79 /* 5.1 v = v/2 */
81 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) { 80 if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
82 goto __ERR; 81 goto LBL_ERR;
83 } 82 }
84 /* 5.2 if D is odd then */ 83 /* 5.2 if D is odd then */
85 if (mp_isodd (&D) == 1) { 84 if (mp_isodd (&D) == 1) {
86 /* D = (D-x)/2 */ 85 /* D = (D-x)/2 */
87 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) { 86 if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
88 goto __ERR; 87 goto LBL_ERR;
89 } 88 }
90 } 89 }
91 /* D = D/2 */ 90 /* D = D/2 */
92 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) { 91 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
93 goto __ERR; 92 goto LBL_ERR;
94 } 93 }
95 } 94 }
96 95
97 /* 6. if u >= v then */ 96 /* 6. if u >= v then */
98 if (mp_cmp (&u, &v) != MP_LT) { 97 if (mp_cmp (&u, &v) != MP_LT) {
99 /* u = u - v, B = B - D */ 98 /* u = u - v, B = B - D */
100 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) { 99 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
101 goto __ERR; 100 goto LBL_ERR;
102 } 101 }
103 102
104 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) { 103 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
105 goto __ERR; 104 goto LBL_ERR;
106 } 105 }
107 } else { 106 } else {
108 /* v - v - u, D = D - B */ 107 /* v - v - u, D = D - B */
109 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) { 108 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
110 goto __ERR; 109 goto LBL_ERR;
111 } 110 }
112 111
113 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) { 112 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
114 goto __ERR; 113 goto LBL_ERR;
115 } 114 }
116 } 115 }
117 116
118 /* if not zero goto step 4 */ 117 /* if not zero goto step 4 */
119 if (mp_iszero (&u) == 0) { 118 if (mp_iszero (&u) == 0) {
123 /* now a = C, b = D, gcd == g*v */ 122 /* now a = C, b = D, gcd == g*v */
124 123
125 /* if v != 1 then there is no inverse */ 124 /* if v != 1 then there is no inverse */
126 if (mp_cmp_d (&v, 1) != MP_EQ) { 125 if (mp_cmp_d (&v, 1) != MP_EQ) {
127 res = MP_VAL; 126 res = MP_VAL;
128 goto __ERR; 127 goto LBL_ERR;
129 } 128 }
130 129
131 /* b is now the inverse */ 130 /* b is now the inverse */
132 neg = a->sign; 131 neg = a->sign;
133 while (D.sign == MP_NEG) { 132 while (D.sign == MP_NEG) {
134 if ((res = mp_add (&D, b, &D)) != MP_OKAY) { 133 if ((res = mp_add (&D, b, &D)) != MP_OKAY) {
135 goto __ERR; 134 goto LBL_ERR;
136 } 135 }
137 } 136 }
138 mp_exch (&D, c); 137 mp_exch (&D, c);
139 c->sign = neg; 138 c->sign = neg;
140 res = MP_OKAY; 139 res = MP_OKAY;
141 140
142 __ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL); 141 LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
143 return res; 142 return res;
144 } 143 }
145 #endif 144 #endif