Mercurial > dropbear

comparison libtommath/bn_mp_toom_sqr.c @ 1655:f52919ffd3b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents 8bba51a55704
children
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include <tommath_private.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.
7 * 7 *
8 * The library was designed directly after the MPI library by 8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with 9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * SPDX-License-Identifier: Unlicense
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */ 13 */
17 14
18 /* squaring using Toom-Cook 3-way algorithm */ 15 /* squaring using Toom-Cook 3-way algorithm */
19 int 16 int mp_toom_sqr(const mp_int *a, mp_int *b)
20 mp_toom_sqr(mp_int *a, mp_int *b)
21 { 17 {
22 mp_int w0, w1, w2, w3, w4, tmp1, a0, a1, a2; 18 mp_int w0, w1, w2, w3, w4, tmp1, a0, a1, a2;
23 int res, B; 19 int res, B;
24 20
25 /* init temps */ 21 /* init temps */
26 if ((res = mp_init_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL)) != MP_OKAY) { 22 if ((res = mp_init_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL)) != MP_OKAY) {
27 return res; 23 return res;
28 } 24 }
29 25
30 /* B */ 26 /* B */
31 B = a->used / 3; 27 B = a->used / 3;
32 28
33 /* a = a2 * B**2 + a1 * B + a0 */ 29 /* a = a2 * B**2 + a1 * B + a0 */
34 if ((res = mp_mod_2d(a, DIGIT_BIT * B, &a0)) != MP_OKAY) { 30 if ((res = mp_mod_2d(a, DIGIT_BIT * B, &a0)) != MP_OKAY) {
35 goto ERR; 31 goto LBL_ERR;
36 } 32 }
37 33
38 if ((res = mp_copy(a, &a1)) != MP_OKAY) { 34 if ((res = mp_copy(a, &a1)) != MP_OKAY) {
39 goto ERR; 35 goto LBL_ERR;
40 } 36 }
41 mp_rshd(&a1, B); 37 mp_rshd(&a1, B);
42 if ((res = mp_mod_2d(&a1, DIGIT_BIT * B, &a1)) != MP_OKAY) { 38 if ((res = mp_mod_2d(&a1, DIGIT_BIT * B, &a1)) != MP_OKAY) {
43 goto ERR; 39 goto LBL_ERR;
44 } 40 }
45 41
46 if ((res = mp_copy(a, &a2)) != MP_OKAY) { 42 if ((res = mp_copy(a, &a2)) != MP_OKAY) {
47 goto ERR; 43 goto LBL_ERR;
48 } 44 }
49 mp_rshd(&a2, B*2); 45 mp_rshd(&a2, B*2);
50 46
51 /* w0 = a0*a0 */ 47 /* w0 = a0*a0 */
52 if ((res = mp_sqr(&a0, &w0)) != MP_OKAY) { 48 if ((res = mp_sqr(&a0, &w0)) != MP_OKAY) {
53 goto ERR; 49 goto LBL_ERR;
54 } 50 }
55 51
56 /* w4 = a2 * a2 */ 52 /* w4 = a2 * a2 */
57 if ((res = mp_sqr(&a2, &w4)) != MP_OKAY) { 53 if ((res = mp_sqr(&a2, &w4)) != MP_OKAY) {
58 goto ERR; 54 goto LBL_ERR;
59 } 55 }
60 56
61 /* w1 = (a2 + 2(a1 + 2a0))**2 */ 57 /* w1 = (a2 + 2(a1 + 2a0))**2 */
62 if ((res = mp_mul_2(&a0, &tmp1)) != MP_OKAY) { 58 if ((res = mp_mul_2(&a0, &tmp1)) != MP_OKAY) {
63 goto ERR; 59 goto LBL_ERR;
64 } 60 }
65 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { 61 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) {
66 goto ERR; 62 goto LBL_ERR;
67 } 63 }
68 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { 64 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) {
69 goto ERR; 65 goto LBL_ERR;
70 } 66 }
71 if ((res = mp_add(&tmp1, &a2, &tmp1)) != MP_OKAY) { 67 if ((res = mp_add(&tmp1, &a2, &tmp1)) != MP_OKAY) {
72 goto ERR; 68 goto LBL_ERR;
73 } 69 }
74 70
75 if ((res = mp_sqr(&tmp1, &w1)) != MP_OKAY) { 71 if ((res = mp_sqr(&tmp1, &w1)) != MP_OKAY) {
76 goto ERR; 72 goto LBL_ERR;
77 } 73 }
78 74
79 /* w3 = (a0 + 2(a1 + 2a2))**2 */ 75 /* w3 = (a0 + 2(a1 + 2a2))**2 */
80 if ((res = mp_mul_2(&a2, &tmp1)) != MP_OKAY) { 76 if ((res = mp_mul_2(&a2, &tmp1)) != MP_OKAY) {
81 goto ERR; 77 goto LBL_ERR;
82 } 78 }
83 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { 79 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) {
84 goto ERR; 80 goto LBL_ERR;
85 } 81 }
86 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { 82 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) {
87 goto ERR; 83 goto LBL_ERR;
88 } 84 }
89 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { 85 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) {
90 goto ERR; 86 goto LBL_ERR;
91 } 87 }
92 88
93 if ((res = mp_sqr(&tmp1, &w3)) != MP_OKAY) { 89 if ((res = mp_sqr(&tmp1, &w3)) != MP_OKAY) {
94 goto ERR; 90 goto LBL_ERR;
95 } 91 }
96 92
97 93
98 /* w2 = (a2 + a1 + a0)**2 */ 94 /* w2 = (a2 + a1 + a0)**2 */
99 if ((res = mp_add(&a2, &a1, &tmp1)) != MP_OKAY) { 95 if ((res = mp_add(&a2, &a1, &tmp1)) != MP_OKAY) {
100 goto ERR; 96 goto LBL_ERR;
101 } 97 }
102 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { 98 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) {
103 goto ERR; 99 goto LBL_ERR;
104 } 100 }
105 if ((res = mp_sqr(&tmp1, &w2)) != MP_OKAY) { 101 if ((res = mp_sqr(&tmp1, &w2)) != MP_OKAY) {
106 goto ERR; 102 goto LBL_ERR;
107 } 103 }
108 104
109 /* now solve the matrix 105 /* now solve the matrix
110 106
111 0 0 0 0 1 107 0 0 0 0 1
112 1 2 4 8 16 108 1 2 4 8 16
113 1 1 1 1 1 109 1 1 1 1 1
114 16 8 4 2 1 110 16 8 4 2 1
115 1 0 0 0 0 111 1 0 0 0 0
116 112
117 using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication. 113 using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication.
118 */ 114 */
119 115
120 /* r1 - r4 */ 116 /* r1 - r4 */
121 if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) { 117 if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) {
122 goto ERR; 118 goto LBL_ERR;
123 } 119 }
124 /* r3 - r0 */ 120 /* r3 - r0 */
125 if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) { 121 if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) {
126 goto ERR; 122 goto LBL_ERR;
127 } 123 }
128 /* r1/2 */ 124 /* r1/2 */
129 if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) { 125 if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) {
130 goto ERR; 126 goto LBL_ERR;
131 } 127 }
132 /* r3/2 */ 128 /* r3/2 */
133 if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) { 129 if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) {
134 goto ERR; 130 goto LBL_ERR;
135 } 131 }
136 /* r2 - r0 - r4 */ 132 /* r2 - r0 - r4 */
137 if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) { 133 if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) {
138 goto ERR; 134 goto LBL_ERR;
139 } 135 }
140 if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) { 136 if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) {
141 goto ERR; 137 goto LBL_ERR;
142 } 138 }
143 /* r1 - r2 */ 139 /* r1 - r2 */
144 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 140 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) {
145 goto ERR; 141 goto LBL_ERR;
146 } 142 }
147 /* r3 - r2 */ 143 /* r3 - r2 */
148 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 144 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) {
149 goto ERR; 145 goto LBL_ERR;
150 } 146 }
151 /* r1 - 8r0 */ 147 /* r1 - 8r0 */
152 if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) { 148 if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) {
153 goto ERR; 149 goto LBL_ERR;
154 } 150 }
155 if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) { 151 if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) {
156 goto ERR; 152 goto LBL_ERR;
157 } 153 }
158 /* r3 - 8r4 */ 154 /* r3 - 8r4 */
159 if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) { 155 if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) {
160 goto ERR; 156 goto LBL_ERR;
161 } 157 }
162 if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) { 158 if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) {
163 goto ERR; 159 goto LBL_ERR;
164 } 160 }
165 /* 3r2 - r1 - r3 */ 161 /* 3r2 - r1 - r3 */
166 if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) { 162 if ((res = mp_mul_d(&w2, 3uL, &w2)) != MP_OKAY) {
167 goto ERR; 163 goto LBL_ERR;
168 } 164 }
169 if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) { 165 if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) {
170 goto ERR; 166 goto LBL_ERR;
171 } 167 }
172 if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) { 168 if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) {
173 goto ERR; 169 goto LBL_ERR;
174 } 170 }
175 /* r1 - r2 */ 171 /* r1 - r2 */
176 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { 172 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) {
177 goto ERR; 173 goto LBL_ERR;
178 } 174 }
179 /* r3 - r2 */ 175 /* r3 - r2 */
180 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { 176 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) {
181 goto ERR; 177 goto LBL_ERR;
182 } 178 }
183 /* r1/3 */ 179 /* r1/3 */
184 if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) { 180 if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) {
185 goto ERR; 181 goto LBL_ERR;
186 } 182 }
187 /* r3/3 */ 183 /* r3/3 */
188 if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) { 184 if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) {
189 goto ERR; 185 goto LBL_ERR;
190 } 186 }
191 187
192 /* at this point shift W[n] by B*n */ 188 /* at this point shift W[n] by B*n */
193 if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) { 189 if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) {
194 goto ERR; 190 goto LBL_ERR;
195 } 191 }
196 if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) { 192 if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) {
197 goto ERR; 193 goto LBL_ERR;
198 } 194 }
199 if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) { 195 if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) {
200 goto ERR; 196 goto LBL_ERR;
201 } 197 }
202 if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) { 198 if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) {
203 goto ERR; 199 goto LBL_ERR;
204 } 200 }
205 201
206 if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) { 202 if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) {
207 goto ERR; 203 goto LBL_ERR;
208 } 204 }
209 if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) { 205 if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) {
210 goto ERR; 206 goto LBL_ERR;
211 } 207 }
212 if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) { 208 if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) {
213 goto ERR; 209 goto LBL_ERR;
214 } 210 }
215 if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) { 211 if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) {
216 goto ERR; 212 goto LBL_ERR;
217 } 213 }
218 214
219 ERR: 215 LBL_ERR:
220 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL); 216 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL);
221 return res; 217 return res;
222 } 218 }
223 219
224 #endif 220 #endif
225 221
226 /* ref: $Format:%D$ */ 222 /* ref: HEAD -> master, tag: v1.1.0 */
227 /* git commit: $Format:%H$ */ 223 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
228 /* commit time: $Format:%ai$ */ 224 /* commit time: 2019-01-28 20:32:32 +0100 */