Mercurial > dropbear

comparison libtommath/bn_mp_toom_sqr.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_TOOM_SQR_C 2 #ifdef BN_MP_TOOM_SQR_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 /* squaring using Toom-Cook 3-way algorithm */ 18 /* squaring using Toom-Cook 3-way algorithm */
19 int 19 int
20 mp_toom_sqr(mp_int *a, mp_int *b) 20 mp_toom_sqr(mp_int *a, mp_int *b)
37 37
38 if ((res = mp_copy(a, &a1)) != MP_OKAY) { 38 if ((res = mp_copy(a, &a1)) != MP_OKAY) {
39 goto ERR; 39 goto ERR;
40 } 40 }
41 mp_rshd(&a1, B); 41 mp_rshd(&a1, B);
42 mp_mod_2d(&a1, DIGIT_BIT * B, &a1); 42 if ((res = mp_mod_2d(&a1, DIGIT_BIT * B, &a1)) != MP_OKAY) {
43 goto ERR;
44 }
43 45
44 if ((res = mp_copy(a, &a2)) != MP_OKAY) { 46 if ((res = mp_copy(a, &a2)) != MP_OKAY) {
45 goto ERR; 47 goto ERR;
46 } 48 }
47 mp_rshd(&a2, B*2); 49 mp_rshd(&a2, B*2);
113 1 0 0 0 0 115 1 0 0 0 0
114 116
115 using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication. 117 using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication.
116 */ 118 */
117 119
118 /* r1 - r4 */ 120 /* r1 - r4 */
119 if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) { 121 if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) {
120 goto ERR; 122 goto ERR;
121 } 123 }
122 /* r3 - r0 */ 124 /* r3 - r0 */
123 if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) { 125 if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) {
124 goto ERR; 126 goto ERR;
125 } 127 }
126 /* r1/2 */ 128 /* r1/2 */
127 if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) { 129 if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) {
128 goto ERR; 130 goto ERR;
129 } 131 }
130 /* r3/2 */ 132 /* r3/2 */
131 if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) { 133 if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) {
132 goto ERR; 134 goto ERR;
133 } 135 }
134 /* r2 - r0 - r4 */ 136 /* r2 - r0 - r4 */
135 if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) { 137 if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) {
136 goto ERR; 138 goto ERR;
137 } 139 }
138 if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) { 140 if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) {
139 goto ERR; 141 goto ERR;
140 } 142 }
141 /* r1 - r2 */ 143 /* r1 - r2 */
142 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 144 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) {
143 goto ERR; 145 goto ERR;
144 } 146 }
145 /* r3 - r2 */ 147 /* r3 - r2 */
146 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 148 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) {
147 goto ERR; 149 goto ERR;
148 } 150 }
149 /* r1 - 8r0 */ 151 /* r1 - 8r0 */
150 if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) { 152 if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) {
151 goto ERR; 153 goto ERR;
152 } 154 }
153 if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) { 155 if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) {
154 goto ERR; 156 goto ERR;
155 } 157 }
156 /* r3 - 8r4 */ 158 /* r3 - 8r4 */
157 if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) { 159 if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) {
158 goto ERR; 160 goto ERR;
159 } 161 }
160 if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) { 162 if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) {
161 goto ERR; 163 goto ERR;
162 } 164 }
163 /* 3r2 - r1 - r3 */ 165 /* 3r2 - r1 - r3 */
164 if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) { 166 if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) {
165 goto ERR; 167 goto ERR;
166 } 168 }
167 if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) { 169 if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) {
168 goto ERR; 170 goto ERR;
169 } 171 }
170 if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) { 172 if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) {
171 goto ERR; 173 goto ERR;
172 } 174 }
173 /* r1 - r2 */ 175 /* r1 - r2 */
174 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 176 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) {
175 goto ERR; 177 goto ERR;
176 } 178 }
177 /* r3 - r2 */ 179 /* r3 - r2 */
178 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 180 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) {
179 goto ERR; 181 goto ERR;
180 } 182 }
181 /* r1/3 */ 183 /* r1/3 */
182 if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) { 184 if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) {
183 goto ERR; 185 goto ERR;
184 } 186 }
185 /* r3/3 */ 187 /* r3/3 */
186 if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) { 188 if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) {
187 goto ERR; 189 goto ERR;
188 } 190 }
189 191
190 /* at this point shift W[n] by B*n */ 192 /* at this point shift W[n] by B*n */
191 if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) { 193 if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) {
192 goto ERR; 194 goto ERR;
193 } 195 }
194 if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) { 196 if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) {
195 goto ERR; 197 goto ERR;
196 } 198 }
197 if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) { 199 if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) {
198 goto ERR; 200 goto ERR;
199 } 201 }
200 if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) { 202 if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) {
201 goto ERR; 203 goto ERR;
202 } 204 }
203 205
204 if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) { 206 if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) {
205 goto ERR; 207 goto ERR;
206 } 208 }
207 if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) { 209 if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) {
208 goto ERR; 210 goto ERR;
209 } 211 }
210 if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) { 212 if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) {
211 goto ERR; 213 goto ERR;
212 } 214 }
213 if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) { 215 if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) {
214 goto ERR; 216 goto ERR;
215 } 217 }
216 218
217 ERR: 219 ERR:
218 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL); 220 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL);
219 return res; 221 return res;
220 } 222 }
221 223
222 #endif 224 #endif
223 225
224 /* $Source: /cvs/libtom/libtommath/bn_mp_toom_sqr.c,v $ */ 226 /* $Source$ */
225 /* $Revision: 1.3 $ */ 227 /* $Revision$ */
226 /* $Date: 2006/03/31 14:18:44 $ */ 228 /* $Date$ */