|
1
|
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
2 * |
|
|
3 * LibTomMath is a library that provides multiple-precision |
|
|
4 * integer arithmetic as well as number theoretic functionality. |
|
|
5 * |
|
|
6 * The library was designed directly after the MPI library by |
|
|
7 * Michael Fromberger but has been written from scratch with |
|
|
8 * additional optimizations in place. |
|
|
9 * |
|
|
10 * The library is free for all purposes without any express |
|
|
11 * guarantee it works. |
|
|
12 * |
|
|
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
14 */ |
|
|
15 #include <tommath.h> |
|
|
16 |
|
|
17 /* squaring using Toom-Cook 3-way algorithm */ |
|
|
18 int |
|
|
19 mp_toom_sqr(mp_int *a, mp_int *b) |
|
|
20 { |
|
|
21 mp_int w0, w1, w2, w3, w4, tmp1, a0, a1, a2; |
|
|
22 int res, B; |
|
|
23 |
|
|
24 /* init temps */ |
|
|
25 if ((res = mp_init_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL)) != MP_OKAY) { |
|
|
26 return res; |
|
|
27 } |
|
|
28 |
|
|
29 /* B */ |
|
|
30 B = a->used / 3; |
|
|
31 |
|
|
32 /* a = a2 * B**2 + a1 * B + a0 */ |
|
|
33 if ((res = mp_mod_2d(a, DIGIT_BIT * B, &a0)) != MP_OKAY) { |
|
|
34 goto ERR; |
|
|
35 } |
|
|
36 |
|
|
37 if ((res = mp_copy(a, &a1)) != MP_OKAY) { |
|
|
38 goto ERR; |
|
|
39 } |
|
|
40 mp_rshd(&a1, B); |
|
|
41 mp_mod_2d(&a1, DIGIT_BIT * B, &a1); |
|
|
42 |
|
|
43 if ((res = mp_copy(a, &a2)) != MP_OKAY) { |
|
|
44 goto ERR; |
|
|
45 } |
|
|
46 mp_rshd(&a2, B*2); |
|
|
47 |
|
|
48 /* w0 = a0*a0 */ |
|
|
49 if ((res = mp_sqr(&a0, &w0)) != MP_OKAY) { |
|
|
50 goto ERR; |
|
|
51 } |
|
|
52 |
|
|
53 /* w4 = a2 * a2 */ |
|
|
54 if ((res = mp_sqr(&a2, &w4)) != MP_OKAY) { |
|
|
55 goto ERR; |
|
|
56 } |
|
|
57 |
|
|
58 /* w1 = (a2 + 2(a1 + 2a0))**2 */ |
|
|
59 if ((res = mp_mul_2(&a0, &tmp1)) != MP_OKAY) { |
|
|
60 goto ERR; |
|
|
61 } |
|
|
62 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { |
|
|
63 goto ERR; |
|
|
64 } |
|
|
65 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { |
|
|
66 goto ERR; |
|
|
67 } |
|
|
68 if ((res = mp_add(&tmp1, &a2, &tmp1)) != MP_OKAY) { |
|
|
69 goto ERR; |
|
|
70 } |
|
|
71 |
|
|
72 if ((res = mp_sqr(&tmp1, &w1)) != MP_OKAY) { |
|
|
73 goto ERR; |
|
|
74 } |
|
|
75 |
|
|
76 /* w3 = (a0 + 2(a1 + 2a2))**2 */ |
|
|
77 if ((res = mp_mul_2(&a2, &tmp1)) != MP_OKAY) { |
|
|
78 goto ERR; |
|
|
79 } |
|
|
80 if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) { |
|
|
81 goto ERR; |
|
|
82 } |
|
|
83 if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) { |
|
|
84 goto ERR; |
|
|
85 } |
|
|
86 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { |
|
|
87 goto ERR; |
|
|
88 } |
|
|
89 |
|
|
90 if ((res = mp_sqr(&tmp1, &w3)) != MP_OKAY) { |
|
|
91 goto ERR; |
|
|
92 } |
|
|
93 |
|
|
94 |
|
|
95 /* w2 = (a2 + a1 + a0)**2 */ |
|
|
96 if ((res = mp_add(&a2, &a1, &tmp1)) != MP_OKAY) { |
|
|
97 goto ERR; |
|
|
98 } |
|
|
99 if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) { |
|
|
100 goto ERR; |
|
|
101 } |
|
|
102 if ((res = mp_sqr(&tmp1, &w2)) != MP_OKAY) { |
|
|
103 goto ERR; |
|
|
104 } |
|
|
105 |
|
|
106 /* now solve the matrix |
|
|
107 |
|
|
108 0 0 0 0 1 |
|
|
109 1 2 4 8 16 |
|
|
110 1 1 1 1 1 |
|
|
111 16 8 4 2 1 |
|
|
112 1 0 0 0 0 |
|
|
113 |
|
|
114 using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication. |
|
|
115 */ |
|
|
116 |
|
|
117 /* r1 - r4 */ |
|
|
118 if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) { |
|
|
119 goto ERR; |
|
|
120 } |
|
|
121 /* r3 - r0 */ |
|
|
122 if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) { |
|
|
123 goto ERR; |
|
|
124 } |
|
|
125 /* r1/2 */ |
|
|
126 if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) { |
|
|
127 goto ERR; |
|
|
128 } |
|
|
129 /* r3/2 */ |
|
|
130 if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) { |
|
|
131 goto ERR; |
|
|
132 } |
|
|
133 /* r2 - r0 - r4 */ |
|
|
134 if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) { |
|
|
135 goto ERR; |
|
|
136 } |
|
|
137 if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) { |
|
|
138 goto ERR; |
|
|
139 } |
|
|
140 /* r1 - r2 */ |
|
|
141 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { |
|
|
142 goto ERR; |
|
|
143 } |
|
|
144 /* r3 - r2 */ |
|
|
145 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { |
|
|
146 goto ERR; |
|
|
147 } |
|
|
148 /* r1 - 8r0 */ |
|
|
149 if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) { |
|
|
150 goto ERR; |
|
|
151 } |
|
|
152 if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) { |
|
|
153 goto ERR; |
|
|
154 } |
|
|
155 /* r3 - 8r4 */ |
|
|
156 if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) { |
|
|
157 goto ERR; |
|
|
158 } |
|
|
159 if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) { |
|
|
160 goto ERR; |
|
|
161 } |
|
|
162 /* 3r2 - r1 - r3 */ |
|
|
163 if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) { |
|
|
164 goto ERR; |
|
|
165 } |
|
|
166 if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) { |
|
|
167 goto ERR; |
|
|
168 } |
|
|
169 if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) { |
|
|
170 goto ERR; |
|
|
171 } |
|
|
172 /* r1 - r2 */ |
|
|
173 if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) { |
|
|
174 goto ERR; |
|
|
175 } |
|
|
176 /* r3 - r2 */ |
|
|
177 if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) { |
|
|
178 goto ERR; |
|
|
179 } |
|
|
180 /* r1/3 */ |
|
|
181 if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) { |
|
|
182 goto ERR; |
|
|
183 } |
|
|
184 /* r3/3 */ |
|
|
185 if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) { |
|
|
186 goto ERR; |
|
|
187 } |
|
|
188 |
|
|
189 /* at this point shift W[n] by B*n */ |
|
|
190 if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) { |
|
|
191 goto ERR; |
|
|
192 } |
|
|
193 if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) { |
|
|
194 goto ERR; |
|
|
195 } |
|
|
196 if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) { |
|
|
197 goto ERR; |
|
|
198 } |
|
|
199 if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) { |
|
|
200 goto ERR; |
|
|
201 } |
|
|
202 |
|
|
203 if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) { |
|
|
204 goto ERR; |
|
|
205 } |
|
|
206 if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) { |
|
|
207 goto ERR; |
|
|
208 } |
|
|
209 if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) { |
|
|
210 goto ERR; |
|
|
211 } |
|
|
212 if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) { |
|
|
213 goto ERR; |
|
|
214 } |
|
|
215 |
|
|
216 ERR: |
|
|
217 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL); |
|
|
218 return res; |
|
|
219 } |
|
|
220 |
