Mercurial > dropbear

comparison bn_mp_invmod_slow.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
31 &A, &B, &C, &D, NULL)) != MP_OKAY) { 31 &A, &B, &C, &D, NULL)) != MP_OKAY) {
32 return res; 32 return res;
33 } 33 }
34 34
35 /* x = a, y = b */ 35 /* x = a, y = b */
36 if ((res = mp_copy (a, &x)) != MP_OKAY) { 36 if ((res = mp_mod(a, b, &x)) != MP_OKAY) {
37 goto __ERR; 37 goto LBL_ERR;
38 } 38 }
39 if ((res = mp_copy (b, &y)) != MP_OKAY) { 39 if ((res = mp_copy (b, &y)) != MP_OKAY) {
40 goto __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) == 1 && mp_iseven (&y) == 1) {
45 res = MP_VAL; 45 res = MP_VAL;
46 goto __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 */
50 if ((res = mp_copy (&x, &u)) != MP_OKAY) { 50 if ((res = mp_copy (&x, &u)) != MP_OKAY) {
51 goto __ERR; 51 goto LBL_ERR;
52 } 52 }
53 if ((res = mp_copy (&y, &v)) != MP_OKAY) { 53 if ((res = mp_copy (&y, &v)) != MP_OKAY) {
54 goto __ERR; 54 goto LBL_ERR;
55 } 55 }
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) == 1) {
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 __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) == 1 || mp_isodd (&B) == 1) {
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 __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) {
73 goto __ERR; 73 goto LBL_ERR;
74 } 74 }
75 } 75 }
76 /* A = A/2, B = B/2 */ 76 /* A = A/2, B = B/2 */
77 if ((res = mp_div_2 (&A, &A)) != MP_OKAY) { 77 if ((res = mp_div_2 (&A, &A)) != MP_OKAY) {
78 goto __ERR; 78 goto LBL_ERR;
79 } 79 }
80 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) { 80 if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
81 goto __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) == 1) {
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 __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) == 1 || mp_isodd (&D) == 1) {
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 __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) {
98 goto __ERR; 98 goto LBL_ERR;
99 } 99 }
100 } 100 }
101 /* C = C/2, D = D/2 */ 101 /* C = C/2, D = D/2 */
102 if ((res = mp_div_2 (&C, &C)) != MP_OKAY) { 102 if ((res = mp_div_2 (&C, &C)) != MP_OKAY) {
103 goto __ERR; 103 goto LBL_ERR;
104 } 104 }
105 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) { 105 if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
106 goto __ERR; 106 goto LBL_ERR;
107 } 107 }
108 } 108 }
109 109
110 /* 6. if u >= v then */ 110 /* 6. if u >= v then */
111 if (mp_cmp (&u, &v) != MP_LT) { 111 if (mp_cmp (&u, &v) != MP_LT) {
112 /* u = u - v, A = A - C, B = B - D */ 112 /* u = u - v, A = A - C, B = B - D */
113 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) { 113 if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
114 goto __ERR; 114 goto LBL_ERR;
115 } 115 }
116 116
117 if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) { 117 if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) {
118 goto __ERR; 118 goto LBL_ERR;
119 } 119 }
120 120
121 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) { 121 if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
122 goto __ERR; 122 goto LBL_ERR;
123 } 123 }
124 } else { 124 } else {
125 /* v - v - u, C = C - A, D = D - B */ 125 /* v - v - u, C = C - A, D = D - B */
126 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) { 126 if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
127 goto __ERR; 127 goto LBL_ERR;
128 } 128 }
129 129
130 if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) { 130 if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) {
131 goto __ERR; 131 goto LBL_ERR;
132 } 132 }
133 133
134 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) { 134 if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
135 goto __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) == 0)
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 */
146 if (mp_cmp_d (&v, 1) != MP_EQ) { 146 if (mp_cmp_d (&v, 1) != MP_EQ) {
147 res = MP_VAL; 147 res = MP_VAL;
148 goto __ERR; 148 goto LBL_ERR;
149 } 149 }
150 150
151 /* if its too low */ 151 /* if its too low */
152 while (mp_cmp_d(&C, 0) == MP_LT) { 152 while (mp_cmp_d(&C, 0) == MP_LT) {
153 if ((res = mp_add(&C, b, &C)) != MP_OKAY) { 153 if ((res = mp_add(&C, b, &C)) != MP_OKAY) {
154 goto __ERR; 154 goto LBL_ERR;
155 } 155 }
156 } 156 }
157 157
158 /* too big */ 158 /* too big */
159 while (mp_cmp_mag(&C, b) != MP_LT) { 159 while (mp_cmp_mag(&C, b) != MP_LT) {
160 if ((res = mp_sub(&C, b, &C)) != MP_OKAY) { 160 if ((res = mp_sub(&C, b, &C)) != MP_OKAY) {
161 goto __ERR; 161 goto LBL_ERR;
162 } 162 }
163 } 163 }
164 164
165 /* C is now the inverse */ 165 /* C is now the inverse */
166 mp_exch (&C, c); 166 mp_exch (&C, c);
167 res = MP_OKAY; 167 res = MP_OKAY;
168 __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