Initial adaptations for Curve25519 code.
[openssl.git] / crypto / ec / curve25519.c
1 /* ====================================================================
2  * Copyright (c) 2016 The OpenSSL Project.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  *
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in
13  *    the documentation and/or other materials provided with the
14  *    distribution.
15  *
16  * 3. All advertising materials mentioning features or use of this
17  *    software must display the following acknowledgment:
18  *    "This product includes software developed by the OpenSSL Project
19  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
20  *
21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
22  *    endorse or promote products derived from this software without
23  *    prior written permission. For written permission, please contact
24  *    licensing@OpenSSL.org.
25  *
26  * 5. Products derived from this software may not be called "OpenSSL"
27  *    nor may "OpenSSL" appear in their names without prior written
28  *    permission of the OpenSSL Project.
29  *
30  * 6. Redistributions of any form whatsoever must retain the following
31  *    acknowledgment:
32  *    "This product includes software developed by the OpenSSL Project
33  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
34  *
35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
46  * OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  */
49
50 /* This code is mostly taken from the ref10 version of Ed25519 in SUPERCOP
51  * 20141124 (http://bench.cr.yp.to/supercop.html).
52  *
53  * The field functions are shared by Ed25519 and X25519 where possible. */
54
55 #include <string.h>
56 #include "ec_lcl.h"
57
58
59 /* fe means field element. Here the field is \Z/(2^255-19). An element t,
60  * entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77
61  * t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on
62  * context.  */
63 typedef int32_t fe[10];
64
65 static uint64_t load_3(const uint8_t *in) {
66   uint64_t result;
67   result = (uint64_t)in[0];
68   result |= ((uint64_t)in[1]) << 8;
69   result |= ((uint64_t)in[2]) << 16;
70   return result;
71 }
72
73 static uint64_t load_4(const uint8_t *in) {
74   uint64_t result;
75   result = (uint64_t)in[0];
76   result |= ((uint64_t)in[1]) << 8;
77   result |= ((uint64_t)in[2]) << 16;
78   result |= ((uint64_t)in[3]) << 24;
79   return result;
80 }
81
82 static void fe_frombytes(fe h, const uint8_t *s) {
83   /* Ignores top bit of h. */
84   int64_t h0 = load_4(s);
85   int64_t h1 = load_3(s + 4) << 6;
86   int64_t h2 = load_3(s + 7) << 5;
87   int64_t h3 = load_3(s + 10) << 3;
88   int64_t h4 = load_3(s + 13) << 2;
89   int64_t h5 = load_4(s + 16);
90   int64_t h6 = load_3(s + 20) << 7;
91   int64_t h7 = load_3(s + 23) << 5;
92   int64_t h8 = load_3(s + 26) << 4;
93   int64_t h9 = (load_3(s + 29) & 8388607) << 2;
94   int64_t carry0;
95   int64_t carry1;
96   int64_t carry2;
97   int64_t carry3;
98   int64_t carry4;
99   int64_t carry5;
100   int64_t carry6;
101   int64_t carry7;
102   int64_t carry8;
103   int64_t carry9;
104
105   carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
106   carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
107   carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
108   carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
109   carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
110
111   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
112   carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
113   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
114   carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
115   carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
116
117   h[0] = h0;
118   h[1] = h1;
119   h[2] = h2;
120   h[3] = h3;
121   h[4] = h4;
122   h[5] = h5;
123   h[6] = h6;
124   h[7] = h7;
125   h[8] = h8;
126   h[9] = h9;
127 }
128
129 /* Preconditions:
130  *  |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
131  *
132  * Write p=2^255-19; q=floor(h/p).
133  * Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
134  *
135  * Proof:
136  *   Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
137  *   Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
138  *
139  *   Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
140  *   Then 0<y<1.
141  *
142  *   Write r=h-pq.
143  *   Have 0<=r<=p-1=2^255-20.
144  *   Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
145  *
146  *   Write x=r+19(2^-255)r+y.
147  *   Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
148  *
149  *   Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
150  *   so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q. */
151 static void fe_tobytes(uint8_t *s, const fe h) {
152   int32_t h0 = h[0];
153   int32_t h1 = h[1];
154   int32_t h2 = h[2];
155   int32_t h3 = h[3];
156   int32_t h4 = h[4];
157   int32_t h5 = h[5];
158   int32_t h6 = h[6];
159   int32_t h7 = h[7];
160   int32_t h8 = h[8];
161   int32_t h9 = h[9];
162   int32_t q;
163   int32_t carry0;
164   int32_t carry1;
165   int32_t carry2;
166   int32_t carry3;
167   int32_t carry4;
168   int32_t carry5;
169   int32_t carry6;
170   int32_t carry7;
171   int32_t carry8;
172   int32_t carry9;
173
174   q = (19 * h9 + (((int32_t) 1) << 24)) >> 25;
175   q = (h0 + q) >> 26;
176   q = (h1 + q) >> 25;
177   q = (h2 + q) >> 26;
178   q = (h3 + q) >> 25;
179   q = (h4 + q) >> 26;
180   q = (h5 + q) >> 25;
181   q = (h6 + q) >> 26;
182   q = (h7 + q) >> 25;
183   q = (h8 + q) >> 26;
184   q = (h9 + q) >> 25;
185
186   /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
187   h0 += 19 * q;
188   /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
189
190   carry0 = h0 >> 26; h1 += carry0; h0 -= carry0 << 26;
191   carry1 = h1 >> 25; h2 += carry1; h1 -= carry1 << 25;
192   carry2 = h2 >> 26; h3 += carry2; h2 -= carry2 << 26;
193   carry3 = h3 >> 25; h4 += carry3; h3 -= carry3 << 25;
194   carry4 = h4 >> 26; h5 += carry4; h4 -= carry4 << 26;
195   carry5 = h5 >> 25; h6 += carry5; h5 -= carry5 << 25;
196   carry6 = h6 >> 26; h7 += carry6; h6 -= carry6 << 26;
197   carry7 = h7 >> 25; h8 += carry7; h7 -= carry7 << 25;
198   carry8 = h8 >> 26; h9 += carry8; h8 -= carry8 << 26;
199   carry9 = h9 >> 25;               h9 -= carry9 << 25;
200                   /* h10 = carry9 */
201
202   /* Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
203    * Have h0+...+2^230 h9 between 0 and 2^255-1;
204    * evidently 2^255 h10-2^255 q = 0.
205    * Goal: Output h0+...+2^230 h9.  */
206
207   s[0] = h0 >> 0;
208   s[1] = h0 >> 8;
209   s[2] = h0 >> 16;
210   s[3] = (h0 >> 24) | (h1 << 2);
211   s[4] = h1 >> 6;
212   s[5] = h1 >> 14;
213   s[6] = (h1 >> 22) | (h2 << 3);
214   s[7] = h2 >> 5;
215   s[8] = h2 >> 13;
216   s[9] = (h2 >> 21) | (h3 << 5);
217   s[10] = h3 >> 3;
218   s[11] = h3 >> 11;
219   s[12] = (h3 >> 19) | (h4 << 6);
220   s[13] = h4 >> 2;
221   s[14] = h4 >> 10;
222   s[15] = h4 >> 18;
223   s[16] = h5 >> 0;
224   s[17] = h5 >> 8;
225   s[18] = h5 >> 16;
226   s[19] = (h5 >> 24) | (h6 << 1);
227   s[20] = h6 >> 7;
228   s[21] = h6 >> 15;
229   s[22] = (h6 >> 23) | (h7 << 3);
230   s[23] = h7 >> 5;
231   s[24] = h7 >> 13;
232   s[25] = (h7 >> 21) | (h8 << 4);
233   s[26] = h8 >> 4;
234   s[27] = h8 >> 12;
235   s[28] = (h8 >> 20) | (h9 << 6);
236   s[29] = h9 >> 2;
237   s[30] = h9 >> 10;
238   s[31] = h9 >> 18;
239 }
240
241 /* h = f */
242 static void fe_copy(fe h, const fe f) {
243   memmove(h, f, sizeof(int32_t) * 10);
244 }
245
246 /* h = 0 */
247 static void fe_0(fe h) { memset(h, 0, sizeof(int32_t) * 10); }
248
249 /* h = 1 */
250 static void fe_1(fe h) {
251   memset(h, 0, sizeof(int32_t) * 10);
252   h[0] = 1;
253 }
254
255 /* h = f + g
256  * Can overlap h with f or g.
257  *
258  * Preconditions:
259  *    |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
260  *    |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
261  *
262  * Postconditions:
263  *    |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
264 static void fe_add(fe h, const fe f, const fe g) {
265   unsigned i;
266   for (i = 0; i < 10; i++) {
267     h[i] = f[i] + g[i];
268   }
269 }
270
271 /* h = f - g
272  * Can overlap h with f or g.
273  *
274  * Preconditions:
275  *    |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
276  *    |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
277  *
278  * Postconditions:
279  *    |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
280 static void fe_sub(fe h, const fe f, const fe g) {
281   unsigned i;
282   for (i = 0; i < 10; i++) {
283     h[i] = f[i] - g[i];
284   }
285 }
286
287 /* h = f * g
288  * Can overlap h with f or g.
289  *
290  * Preconditions:
291  *    |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
292  *    |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
293  *
294  * Postconditions:
295  *    |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
296  *
297  * Notes on implementation strategy:
298  *
299  * Using schoolbook multiplication.
300  * Karatsuba would save a little in some cost models.
301  *
302  * Most multiplications by 2 and 19 are 32-bit precomputations;
303  * cheaper than 64-bit postcomputations.
304  *
305  * There is one remaining multiplication by 19 in the carry chain;
306  * one *19 precomputation can be merged into this,
307  * but the resulting data flow is considerably less clean.
308  *
309  * There are 12 carries below.
310  * 10 of them are 2-way parallelizable and vectorizable.
311  * Can get away with 11 carries, but then data flow is much deeper.
312  *
313  * With tighter constraints on inputs can squeeze carries into int32. */
314 static void fe_mul(fe h, const fe f, const fe g) {
315   int32_t f0 = f[0];
316   int32_t f1 = f[1];
317   int32_t f2 = f[2];
318   int32_t f3 = f[3];
319   int32_t f4 = f[4];
320   int32_t f5 = f[5];
321   int32_t f6 = f[6];
322   int32_t f7 = f[7];
323   int32_t f8 = f[8];
324   int32_t f9 = f[9];
325   int32_t g0 = g[0];
326   int32_t g1 = g[1];
327   int32_t g2 = g[2];
328   int32_t g3 = g[3];
329   int32_t g4 = g[4];
330   int32_t g5 = g[5];
331   int32_t g6 = g[6];
332   int32_t g7 = g[7];
333   int32_t g8 = g[8];
334   int32_t g9 = g[9];
335   int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */
336   int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */
337   int32_t g3_19 = 19 * g3;
338   int32_t g4_19 = 19 * g4;
339   int32_t g5_19 = 19 * g5;
340   int32_t g6_19 = 19 * g6;
341   int32_t g7_19 = 19 * g7;
342   int32_t g8_19 = 19 * g8;
343   int32_t g9_19 = 19 * g9;
344   int32_t f1_2 = 2 * f1;
345   int32_t f3_2 = 2 * f3;
346   int32_t f5_2 = 2 * f5;
347   int32_t f7_2 = 2 * f7;
348   int32_t f9_2 = 2 * f9;
349   int64_t f0g0    = f0   * (int64_t) g0;
350   int64_t f0g1    = f0   * (int64_t) g1;
351   int64_t f0g2    = f0   * (int64_t) g2;
352   int64_t f0g3    = f0   * (int64_t) g3;
353   int64_t f0g4    = f0   * (int64_t) g4;
354   int64_t f0g5    = f0   * (int64_t) g5;
355   int64_t f0g6    = f0   * (int64_t) g6;
356   int64_t f0g7    = f0   * (int64_t) g7;
357   int64_t f0g8    = f0   * (int64_t) g8;
358   int64_t f0g9    = f0   * (int64_t) g9;
359   int64_t f1g0    = f1   * (int64_t) g0;
360   int64_t f1g1_2  = f1_2 * (int64_t) g1;
361   int64_t f1g2    = f1   * (int64_t) g2;
362   int64_t f1g3_2  = f1_2 * (int64_t) g3;
363   int64_t f1g4    = f1   * (int64_t) g4;
364   int64_t f1g5_2  = f1_2 * (int64_t) g5;
365   int64_t f1g6    = f1   * (int64_t) g6;
366   int64_t f1g7_2  = f1_2 * (int64_t) g7;
367   int64_t f1g8    = f1   * (int64_t) g8;
368   int64_t f1g9_38 = f1_2 * (int64_t) g9_19;
369   int64_t f2g0    = f2   * (int64_t) g0;
370   int64_t f2g1    = f2   * (int64_t) g1;
371   int64_t f2g2    = f2   * (int64_t) g2;
372   int64_t f2g3    = f2   * (int64_t) g3;
373   int64_t f2g4    = f2   * (int64_t) g4;
374   int64_t f2g5    = f2   * (int64_t) g5;
375   int64_t f2g6    = f2   * (int64_t) g6;
376   int64_t f2g7    = f2   * (int64_t) g7;
377   int64_t f2g8_19 = f2   * (int64_t) g8_19;
378   int64_t f2g9_19 = f2   * (int64_t) g9_19;
379   int64_t f3g0    = f3   * (int64_t) g0;
380   int64_t f3g1_2  = f3_2 * (int64_t) g1;
381   int64_t f3g2    = f3   * (int64_t) g2;
382   int64_t f3g3_2  = f3_2 * (int64_t) g3;
383   int64_t f3g4    = f3   * (int64_t) g4;
384   int64_t f3g5_2  = f3_2 * (int64_t) g5;
385   int64_t f3g6    = f3   * (int64_t) g6;
386   int64_t f3g7_38 = f3_2 * (int64_t) g7_19;
387   int64_t f3g8_19 = f3   * (int64_t) g8_19;
388   int64_t f3g9_38 = f3_2 * (int64_t) g9_19;
389   int64_t f4g0    = f4   * (int64_t) g0;
390   int64_t f4g1    = f4   * (int64_t) g1;
391   int64_t f4g2    = f4   * (int64_t) g2;
392   int64_t f4g3    = f4   * (int64_t) g3;
393   int64_t f4g4    = f4   * (int64_t) g4;
394   int64_t f4g5    = f4   * (int64_t) g5;
395   int64_t f4g6_19 = f4   * (int64_t) g6_19;
396   int64_t f4g7_19 = f4   * (int64_t) g7_19;
397   int64_t f4g8_19 = f4   * (int64_t) g8_19;
398   int64_t f4g9_19 = f4   * (int64_t) g9_19;
399   int64_t f5g0    = f5   * (int64_t) g0;
400   int64_t f5g1_2  = f5_2 * (int64_t) g1;
401   int64_t f5g2    = f5   * (int64_t) g2;
402   int64_t f5g3_2  = f5_2 * (int64_t) g3;
403   int64_t f5g4    = f5   * (int64_t) g4;
404   int64_t f5g5_38 = f5_2 * (int64_t) g5_19;
405   int64_t f5g6_19 = f5   * (int64_t) g6_19;
406   int64_t f5g7_38 = f5_2 * (int64_t) g7_19;
407   int64_t f5g8_19 = f5   * (int64_t) g8_19;
408   int64_t f5g9_38 = f5_2 * (int64_t) g9_19;
409   int64_t f6g0    = f6   * (int64_t) g0;
410   int64_t f6g1    = f6   * (int64_t) g1;
411   int64_t f6g2    = f6   * (int64_t) g2;
412   int64_t f6g3    = f6   * (int64_t) g3;
413   int64_t f6g4_19 = f6   * (int64_t) g4_19;
414   int64_t f6g5_19 = f6   * (int64_t) g5_19;
415   int64_t f6g6_19 = f6   * (int64_t) g6_19;
416   int64_t f6g7_19 = f6   * (int64_t) g7_19;
417   int64_t f6g8_19 = f6   * (int64_t) g8_19;
418   int64_t f6g9_19 = f6   * (int64_t) g9_19;
419   int64_t f7g0    = f7   * (int64_t) g0;
420   int64_t f7g1_2  = f7_2 * (int64_t) g1;
421   int64_t f7g2    = f7   * (int64_t) g2;
422   int64_t f7g3_38 = f7_2 * (int64_t) g3_19;
423   int64_t f7g4_19 = f7   * (int64_t) g4_19;
424   int64_t f7g5_38 = f7_2 * (int64_t) g5_19;
425   int64_t f7g6_19 = f7   * (int64_t) g6_19;
426   int64_t f7g7_38 = f7_2 * (int64_t) g7_19;
427   int64_t f7g8_19 = f7   * (int64_t) g8_19;
428   int64_t f7g9_38 = f7_2 * (int64_t) g9_19;
429   int64_t f8g0    = f8   * (int64_t) g0;
430   int64_t f8g1    = f8   * (int64_t) g1;
431   int64_t f8g2_19 = f8   * (int64_t) g2_19;
432   int64_t f8g3_19 = f8   * (int64_t) g3_19;
433   int64_t f8g4_19 = f8   * (int64_t) g4_19;
434   int64_t f8g5_19 = f8   * (int64_t) g5_19;
435   int64_t f8g6_19 = f8   * (int64_t) g6_19;
436   int64_t f8g7_19 = f8   * (int64_t) g7_19;
437   int64_t f8g8_19 = f8   * (int64_t) g8_19;
438   int64_t f8g9_19 = f8   * (int64_t) g9_19;
439   int64_t f9g0    = f9   * (int64_t) g0;
440   int64_t f9g1_38 = f9_2 * (int64_t) g1_19;
441   int64_t f9g2_19 = f9   * (int64_t) g2_19;
442   int64_t f9g3_38 = f9_2 * (int64_t) g3_19;
443   int64_t f9g4_19 = f9   * (int64_t) g4_19;
444   int64_t f9g5_38 = f9_2 * (int64_t) g5_19;
445   int64_t f9g6_19 = f9   * (int64_t) g6_19;
446   int64_t f9g7_38 = f9_2 * (int64_t) g7_19;
447   int64_t f9g8_19 = f9   * (int64_t) g8_19;
448   int64_t f9g9_38 = f9_2 * (int64_t) g9_19;
449   int64_t h0 = f0g0+f1g9_38+f2g8_19+f3g7_38+f4g6_19+f5g5_38+f6g4_19+f7g3_38+f8g2_19+f9g1_38;
450   int64_t h1 = f0g1+f1g0   +f2g9_19+f3g8_19+f4g7_19+f5g6_19+f6g5_19+f7g4_19+f8g3_19+f9g2_19;
451   int64_t h2 = f0g2+f1g1_2 +f2g0   +f3g9_38+f4g8_19+f5g7_38+f6g6_19+f7g5_38+f8g4_19+f9g3_38;
452   int64_t h3 = f0g3+f1g2   +f2g1   +f3g0   +f4g9_19+f5g8_19+f6g7_19+f7g6_19+f8g5_19+f9g4_19;
453   int64_t h4 = f0g4+f1g3_2 +f2g2   +f3g1_2 +f4g0   +f5g9_38+f6g8_19+f7g7_38+f8g6_19+f9g5_38;
454   int64_t h5 = f0g5+f1g4   +f2g3   +f3g2   +f4g1   +f5g0   +f6g9_19+f7g8_19+f8g7_19+f9g6_19;
455   int64_t h6 = f0g6+f1g5_2 +f2g4   +f3g3_2 +f4g2   +f5g1_2 +f6g0   +f7g9_38+f8g8_19+f9g7_38;
456   int64_t h7 = f0g7+f1g6   +f2g5   +f3g4   +f4g3   +f5g2   +f6g1   +f7g0   +f8g9_19+f9g8_19;
457   int64_t h8 = f0g8+f1g7_2 +f2g6   +f3g5_2 +f4g4   +f5g3_2 +f6g2   +f7g1_2 +f8g0   +f9g9_38;
458   int64_t h9 = f0g9+f1g8   +f2g7   +f3g6   +f4g5   +f5g4   +f6g3   +f7g2   +f8g1   +f9g0   ;
459   int64_t carry0;
460   int64_t carry1;
461   int64_t carry2;
462   int64_t carry3;
463   int64_t carry4;
464   int64_t carry5;
465   int64_t carry6;
466   int64_t carry7;
467   int64_t carry8;
468   int64_t carry9;
469
470   /* |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38))
471    *   i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8
472    * |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19))
473    *   i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9 */
474
475   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
476   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
477   /* |h0| <= 2^25 */
478   /* |h4| <= 2^25 */
479   /* |h1| <= 1.71*2^59 */
480   /* |h5| <= 1.71*2^59 */
481
482   carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
483   carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
484   /* |h1| <= 2^24; from now on fits into int32 */
485   /* |h5| <= 2^24; from now on fits into int32 */
486   /* |h2| <= 1.41*2^60 */
487   /* |h6| <= 1.41*2^60 */
488
489   carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
490   carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
491   /* |h2| <= 2^25; from now on fits into int32 unchanged */
492   /* |h6| <= 2^25; from now on fits into int32 unchanged */
493   /* |h3| <= 1.71*2^59 */
494   /* |h7| <= 1.71*2^59 */
495
496   carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
497   carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
498   /* |h3| <= 2^24; from now on fits into int32 unchanged */
499   /* |h7| <= 2^24; from now on fits into int32 unchanged */
500   /* |h4| <= 1.72*2^34 */
501   /* |h8| <= 1.41*2^60 */
502
503   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
504   carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
505   /* |h4| <= 2^25; from now on fits into int32 unchanged */
506   /* |h8| <= 2^25; from now on fits into int32 unchanged */
507   /* |h5| <= 1.01*2^24 */
508   /* |h9| <= 1.71*2^59 */
509
510   carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
511   /* |h9| <= 2^24; from now on fits into int32 unchanged */
512   /* |h0| <= 1.1*2^39 */
513
514   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
515   /* |h0| <= 2^25; from now on fits into int32 unchanged */
516   /* |h1| <= 1.01*2^24 */
517
518   h[0] = h0;
519   h[1] = h1;
520   h[2] = h2;
521   h[3] = h3;
522   h[4] = h4;
523   h[5] = h5;
524   h[6] = h6;
525   h[7] = h7;
526   h[8] = h8;
527   h[9] = h9;
528 }
529
530 /* h = f * f
531  * Can overlap h with f.
532  *
533  * Preconditions:
534  *    |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
535  *
536  * Postconditions:
537  *    |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
538  *
539  * See fe_mul.c for discussion of implementation strategy. */
540 static void fe_sq(fe h, const fe f) {
541   int32_t f0 = f[0];
542   int32_t f1 = f[1];
543   int32_t f2 = f[2];
544   int32_t f3 = f[3];
545   int32_t f4 = f[4];
546   int32_t f5 = f[5];
547   int32_t f6 = f[6];
548   int32_t f7 = f[7];
549   int32_t f8 = f[8];
550   int32_t f9 = f[9];
551   int32_t f0_2 = 2 * f0;
552   int32_t f1_2 = 2 * f1;
553   int32_t f2_2 = 2 * f2;
554   int32_t f3_2 = 2 * f3;
555   int32_t f4_2 = 2 * f4;
556   int32_t f5_2 = 2 * f5;
557   int32_t f6_2 = 2 * f6;
558   int32_t f7_2 = 2 * f7;
559   int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
560   int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
561   int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
562   int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
563   int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
564   int64_t f0f0    = f0   * (int64_t) f0;
565   int64_t f0f1_2  = f0_2 * (int64_t) f1;
566   int64_t f0f2_2  = f0_2 * (int64_t) f2;
567   int64_t f0f3_2  = f0_2 * (int64_t) f3;
568   int64_t f0f4_2  = f0_2 * (int64_t) f4;
569   int64_t f0f5_2  = f0_2 * (int64_t) f5;
570   int64_t f0f6_2  = f0_2 * (int64_t) f6;
571   int64_t f0f7_2  = f0_2 * (int64_t) f7;
572   int64_t f0f8_2  = f0_2 * (int64_t) f8;
573   int64_t f0f9_2  = f0_2 * (int64_t) f9;
574   int64_t f1f1_2  = f1_2 * (int64_t) f1;
575   int64_t f1f2_2  = f1_2 * (int64_t) f2;
576   int64_t f1f3_4  = f1_2 * (int64_t) f3_2;
577   int64_t f1f4_2  = f1_2 * (int64_t) f4;
578   int64_t f1f5_4  = f1_2 * (int64_t) f5_2;
579   int64_t f1f6_2  = f1_2 * (int64_t) f6;
580   int64_t f1f7_4  = f1_2 * (int64_t) f7_2;
581   int64_t f1f8_2  = f1_2 * (int64_t) f8;
582   int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
583   int64_t f2f2    = f2   * (int64_t) f2;
584   int64_t f2f3_2  = f2_2 * (int64_t) f3;
585   int64_t f2f4_2  = f2_2 * (int64_t) f4;
586   int64_t f2f5_2  = f2_2 * (int64_t) f5;
587   int64_t f2f6_2  = f2_2 * (int64_t) f6;
588   int64_t f2f7_2  = f2_2 * (int64_t) f7;
589   int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
590   int64_t f2f9_38 = f2   * (int64_t) f9_38;
591   int64_t f3f3_2  = f3_2 * (int64_t) f3;
592   int64_t f3f4_2  = f3_2 * (int64_t) f4;
593   int64_t f3f5_4  = f3_2 * (int64_t) f5_2;
594   int64_t f3f6_2  = f3_2 * (int64_t) f6;
595   int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
596   int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
597   int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
598   int64_t f4f4    = f4   * (int64_t) f4;
599   int64_t f4f5_2  = f4_2 * (int64_t) f5;
600   int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
601   int64_t f4f7_38 = f4   * (int64_t) f7_38;
602   int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
603   int64_t f4f9_38 = f4   * (int64_t) f9_38;
604   int64_t f5f5_38 = f5   * (int64_t) f5_38;
605   int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
606   int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
607   int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
608   int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
609   int64_t f6f6_19 = f6   * (int64_t) f6_19;
610   int64_t f6f7_38 = f6   * (int64_t) f7_38;
611   int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
612   int64_t f6f9_38 = f6   * (int64_t) f9_38;
613   int64_t f7f7_38 = f7   * (int64_t) f7_38;
614   int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
615   int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
616   int64_t f8f8_19 = f8   * (int64_t) f8_19;
617   int64_t f8f9_38 = f8   * (int64_t) f9_38;
618   int64_t f9f9_38 = f9   * (int64_t) f9_38;
619   int64_t h0 = f0f0  +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;
620   int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;
621   int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;
622   int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;
623   int64_t h4 = f0f4_2+f1f3_4 +f2f2   +f5f9_76+f6f8_38+f7f7_38;
624   int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;
625   int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;
626   int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;
627   int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4   +f9f9_38;
628   int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;
629   int64_t carry0;
630   int64_t carry1;
631   int64_t carry2;
632   int64_t carry3;
633   int64_t carry4;
634   int64_t carry5;
635   int64_t carry6;
636   int64_t carry7;
637   int64_t carry8;
638   int64_t carry9;
639
640   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
641   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
642
643   carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
644   carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
645
646   carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
647   carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
648
649   carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
650   carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
651
652   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
653   carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
654
655   carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
656
657   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
658
659   h[0] = h0;
660   h[1] = h1;
661   h[2] = h2;
662   h[3] = h3;
663   h[4] = h4;
664   h[5] = h5;
665   h[6] = h6;
666   h[7] = h7;
667   h[8] = h8;
668   h[9] = h9;
669 }
670
671 static void fe_invert(fe out, const fe z) {
672   fe t0;
673   fe t1;
674   fe t2;
675   fe t3;
676   int i;
677
678   fe_sq(t0, z);
679   for (i = 1; i < 1; ++i) {
680     fe_sq(t0, t0);
681   }
682   fe_sq(t1, t0);
683   for (i = 1; i < 2; ++i) {
684     fe_sq(t1, t1);
685   }
686   fe_mul(t1, z, t1);
687   fe_mul(t0, t0, t1);
688   fe_sq(t2, t0);
689   for (i = 1; i < 1; ++i) {
690     fe_sq(t2, t2);
691   }
692   fe_mul(t1, t1, t2);
693   fe_sq(t2, t1);
694   for (i = 1; i < 5; ++i) {
695     fe_sq(t2, t2);
696   }
697   fe_mul(t1, t2, t1);
698   fe_sq(t2, t1);
699   for (i = 1; i < 10; ++i) {
700     fe_sq(t2, t2);
701   }
702   fe_mul(t2, t2, t1);
703   fe_sq(t3, t2);
704   for (i = 1; i < 20; ++i) {
705     fe_sq(t3, t3);
706   }
707   fe_mul(t2, t3, t2);
708   fe_sq(t2, t2);
709   for (i = 1; i < 10; ++i) {
710     fe_sq(t2, t2);
711   }
712   fe_mul(t1, t2, t1);
713   fe_sq(t2, t1);
714   for (i = 1; i < 50; ++i) {
715     fe_sq(t2, t2);
716   }
717   fe_mul(t2, t2, t1);
718   fe_sq(t3, t2);
719   for (i = 1; i < 100; ++i) {
720     fe_sq(t3, t3);
721   }
722   fe_mul(t2, t3, t2);
723   fe_sq(t2, t2);
724   for (i = 1; i < 50; ++i) {
725     fe_sq(t2, t2);
726   }
727   fe_mul(t1, t2, t1);
728   fe_sq(t1, t1);
729   for (i = 1; i < 5; ++i) {
730     fe_sq(t1, t1);
731   }
732   fe_mul(out, t1, t0);
733 }
734
735 #if 0 /* Ed25519 code: not used yet */
736
737 /* h = -f
738  *
739  * Preconditions:
740  *    |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
741  *
742  * Postconditions:
743  *    |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. */
744 static void fe_neg(fe h, const fe f) {
745   unsigned i;
746   for (i = 0; i < 10; i++) {
747     h[i] = -f[i];
748   }
749 }
750
751 /* Replace (f,g) with (g,g) if b == 1;
752  * replace (f,g) with (f,g) if b == 0.
753  *
754  * Preconditions: b in {0,1}. */
755 static void fe_cmov(fe f, const fe g, unsigned b) {
756   size_t i;
757   b = 0-b;
758   for (i = 0; i < 10; i++) {
759     int32_t x = f[i] ^ g[i];
760     x &= b;
761     f[i] ^= x;
762   }
763 }
764
765 /* return 0 if f == 0
766  * return 1 if f != 0
767  *
768  * Preconditions:
769  *    |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
770 static int fe_isnonzero(const fe f) {
771   uint8_t s[32];
772   static const uint8_t zero[32] = {0};
773
774   fe_tobytes(s, f);
775   return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0;
776 }
777
778 /* return 1 if f is in {1,3,5,...,q-2}
779  * return 0 if f is in {0,2,4,...,q-1}
780  *
781  * Preconditions:
782  *    |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
783 static int fe_isnegative(const fe f) {
784   uint8_t s[32];
785   fe_tobytes(s, f);
786   return s[0] & 1;
787 }
788
789 /* h = 2 * f * f
790  * Can overlap h with f.
791  *
792  * Preconditions:
793  *    |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
794  *
795  * Postconditions:
796  *    |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
797  *
798  * See fe_mul.c for discussion of implementation strategy. */
799 static void fe_sq2(fe h, const fe f) {
800   int32_t f0 = f[0];
801   int32_t f1 = f[1];
802   int32_t f2 = f[2];
803   int32_t f3 = f[3];
804   int32_t f4 = f[4];
805   int32_t f5 = f[5];
806   int32_t f6 = f[6];
807   int32_t f7 = f[7];
808   int32_t f8 = f[8];
809   int32_t f9 = f[9];
810   int32_t f0_2 = 2 * f0;
811   int32_t f1_2 = 2 * f1;
812   int32_t f2_2 = 2 * f2;
813   int32_t f3_2 = 2 * f3;
814   int32_t f4_2 = 2 * f4;
815   int32_t f5_2 = 2 * f5;
816   int32_t f6_2 = 2 * f6;
817   int32_t f7_2 = 2 * f7;
818   int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
819   int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
820   int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
821   int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
822   int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
823   int64_t f0f0    = f0   * (int64_t) f0;
824   int64_t f0f1_2  = f0_2 * (int64_t) f1;
825   int64_t f0f2_2  = f0_2 * (int64_t) f2;
826   int64_t f0f3_2  = f0_2 * (int64_t) f3;
827   int64_t f0f4_2  = f0_2 * (int64_t) f4;
828   int64_t f0f5_2  = f0_2 * (int64_t) f5;
829   int64_t f0f6_2  = f0_2 * (int64_t) f6;
830   int64_t f0f7_2  = f0_2 * (int64_t) f7;
831   int64_t f0f8_2  = f0_2 * (int64_t) f8;
832   int64_t f0f9_2  = f0_2 * (int64_t) f9;
833   int64_t f1f1_2  = f1_2 * (int64_t) f1;
834   int64_t f1f2_2  = f1_2 * (int64_t) f2;
835   int64_t f1f3_4  = f1_2 * (int64_t) f3_2;
836   int64_t f1f4_2  = f1_2 * (int64_t) f4;
837   int64_t f1f5_4  = f1_2 * (int64_t) f5_2;
838   int64_t f1f6_2  = f1_2 * (int64_t) f6;
839   int64_t f1f7_4  = f1_2 * (int64_t) f7_2;
840   int64_t f1f8_2  = f1_2 * (int64_t) f8;
841   int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
842   int64_t f2f2    = f2   * (int64_t) f2;
843   int64_t f2f3_2  = f2_2 * (int64_t) f3;
844   int64_t f2f4_2  = f2_2 * (int64_t) f4;
845   int64_t f2f5_2  = f2_2 * (int64_t) f5;
846   int64_t f2f6_2  = f2_2 * (int64_t) f6;
847   int64_t f2f7_2  = f2_2 * (int64_t) f7;
848   int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
849   int64_t f2f9_38 = f2   * (int64_t) f9_38;
850   int64_t f3f3_2  = f3_2 * (int64_t) f3;
851   int64_t f3f4_2  = f3_2 * (int64_t) f4;
852   int64_t f3f5_4  = f3_2 * (int64_t) f5_2;
853   int64_t f3f6_2  = f3_2 * (int64_t) f6;
854   int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
855   int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
856   int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
857   int64_t f4f4    = f4   * (int64_t) f4;
858   int64_t f4f5_2  = f4_2 * (int64_t) f5;
859   int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
860   int64_t f4f7_38 = f4   * (int64_t) f7_38;
861   int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
862   int64_t f4f9_38 = f4   * (int64_t) f9_38;
863   int64_t f5f5_38 = f5   * (int64_t) f5_38;
864   int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
865   int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
866   int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
867   int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
868   int64_t f6f6_19 = f6   * (int64_t) f6_19;
869   int64_t f6f7_38 = f6   * (int64_t) f7_38;
870   int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
871   int64_t f6f9_38 = f6   * (int64_t) f9_38;
872   int64_t f7f7_38 = f7   * (int64_t) f7_38;
873   int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
874   int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
875   int64_t f8f8_19 = f8   * (int64_t) f8_19;
876   int64_t f8f9_38 = f8   * (int64_t) f9_38;
877   int64_t f9f9_38 = f9   * (int64_t) f9_38;
878   int64_t h0 = f0f0  +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;
879   int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;
880   int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;
881   int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;
882   int64_t h4 = f0f4_2+f1f3_4 +f2f2   +f5f9_76+f6f8_38+f7f7_38;
883   int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;
884   int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;
885   int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;
886   int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4   +f9f9_38;
887   int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;
888   int64_t carry0;
889   int64_t carry1;
890   int64_t carry2;
891   int64_t carry3;
892   int64_t carry4;
893   int64_t carry5;
894   int64_t carry6;
895   int64_t carry7;
896   int64_t carry8;
897   int64_t carry9;
898
899   h0 += h0;
900   h1 += h1;
901   h2 += h2;
902   h3 += h3;
903   h4 += h4;
904   h5 += h5;
905   h6 += h6;
906   h7 += h7;
907   h8 += h8;
908   h9 += h9;
909
910   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
911   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
912
913   carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
914   carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
915
916   carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
917   carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
918
919   carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
920   carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
921
922   carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
923   carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
924
925   carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
926
927   carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
928
929   h[0] = h0;
930   h[1] = h1;
931   h[2] = h2;
932   h[3] = h3;
933   h[4] = h4;
934   h[5] = h5;
935   h[6] = h6;
936   h[7] = h7;
937   h[8] = h8;
938   h[9] = h9;
939 }
940
941 static void fe_pow22523(fe out, const fe z) {
942   fe t0;
943   fe t1;
944   fe t2;
945   int i;
946
947   fe_sq(t0, z);
948   for (i = 1; i < 1; ++i) {
949     fe_sq(t0, t0);
950   }
951   fe_sq(t1, t0);
952   for (i = 1; i < 2; ++i) {
953     fe_sq(t1, t1);
954   }
955   fe_mul(t1, z, t1);
956   fe_mul(t0, t0, t1);
957   fe_sq(t0, t0);
958   for (i = 1; i < 1; ++i) {
959     fe_sq(t0, t0);
960   }
961   fe_mul(t0, t1, t0);
962   fe_sq(t1, t0);
963   for (i = 1; i < 5; ++i) {
964     fe_sq(t1, t1);
965   }
966   fe_mul(t0, t1, t0);
967   fe_sq(t1, t0);
968   for (i = 1; i < 10; ++i) {
969     fe_sq(t1, t1);
970   }
971   fe_mul(t1, t1, t0);
972   fe_sq(t2, t1);
973   for (i = 1; i < 20; ++i) {
974     fe_sq(t2, t2);
975   }
976   fe_mul(t1, t2, t1);
977   fe_sq(t1, t1);
978   for (i = 1; i < 10; ++i) {
979     fe_sq(t1, t1);
980   }
981   fe_mul(t0, t1, t0);
982   fe_sq(t1, t0);
983   for (i = 1; i < 50; ++i) {
984     fe_sq(t1, t1);
985   }
986   fe_mul(t1, t1, t0);
987   fe_sq(t2, t1);
988   for (i = 1; i < 100; ++i) {
989     fe_sq(t2, t2);
990   }
991   fe_mul(t1, t2, t1);
992   fe_sq(t1, t1);
993   for (i = 1; i < 50; ++i) {
994     fe_sq(t1, t1);
995   }
996   fe_mul(t0, t1, t0);
997   fe_sq(t0, t0);
998   for (i = 1; i < 2; ++i) {
999     fe_sq(t0, t0);
1000   }
1001   fe_mul(out, t0, z);
1002 }
1003
1004 /* ge means group element.
1005
1006  * Here the group is the set of pairs (x,y) of field elements (see fe.h)
1007  * satisfying -x^2 + y^2 = 1 + d x^2y^2
1008  * where d = -121665/121666.
1009  *
1010  * Representations:
1011  *   ge_p2 (projective): (X:Y:Z) satisfying x=X/Z, y=Y/Z
1012  *   ge_p3 (extended): (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
1013  *   ge_p1p1 (completed): ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T
1014  *   ge_precomp (Duif): (y+x,y-x,2dxy) */
1015
1016 typedef struct {
1017   fe X;
1018   fe Y;
1019   fe Z;
1020 } ge_p2;
1021
1022 typedef struct {
1023   fe X;
1024   fe Y;
1025   fe Z;
1026   fe T;
1027 } ge_p3;
1028
1029 typedef struct {
1030   fe X;
1031   fe Y;
1032   fe Z;
1033   fe T;
1034 } ge_p1p1;
1035
1036 typedef struct {
1037   fe yplusx;
1038   fe yminusx;
1039   fe xy2d;
1040 } ge_precomp;
1041
1042 typedef struct {
1043   fe YplusX;
1044   fe YminusX;
1045   fe Z;
1046   fe T2d;
1047 } ge_cached;
1048
1049 static void ge_tobytes(uint8_t *s, const ge_p2 *h) {
1050   fe recip;
1051   fe x;
1052   fe y;
1053
1054   fe_invert(recip, h->Z);
1055   fe_mul(x, h->X, recip);
1056   fe_mul(y, h->Y, recip);
1057   fe_tobytes(s, y);
1058   s[31] ^= fe_isnegative(x) << 7;
1059 }
1060
1061 static void ge_p3_tobytes(uint8_t *s, const ge_p3 *h) {
1062   fe recip;
1063   fe x;
1064   fe y;
1065
1066   fe_invert(recip, h->Z);
1067   fe_mul(x, h->X, recip);
1068   fe_mul(y, h->Y, recip);
1069   fe_tobytes(s, y);
1070   s[31] ^= fe_isnegative(x) << 7;
1071 }
1072
1073 static const fe d = {-10913610, 13857413, -15372611, 6949391,   114729,
1074                      -8787816,  -6275908, -3247719,  -18696448, -12055116};
1075
1076 static const fe sqrtm1 = {-32595792, -7943725,  9377950,  3500415, 12389472,
1077                           -272473,   -25146209, -2005654, 326686,  11406482};
1078
1079 static int ge_frombytes_negate_vartime(ge_p3 *h, const uint8_t *s) {
1080   fe u;
1081   fe v;
1082   fe v3;
1083   fe vxx;
1084   fe check;
1085
1086   fe_frombytes(h->Y, s);
1087   fe_1(h->Z);
1088   fe_sq(u, h->Y);
1089   fe_mul(v, u, d);
1090   fe_sub(u, u, h->Z); /* u = y^2-1 */
1091   fe_add(v, v, h->Z); /* v = dy^2+1 */
1092
1093   fe_sq(v3, v);
1094   fe_mul(v3, v3, v); /* v3 = v^3 */
1095   fe_sq(h->X, v3);
1096   fe_mul(h->X, h->X, v);
1097   fe_mul(h->X, h->X, u); /* x = uv^7 */
1098
1099   fe_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */
1100   fe_mul(h->X, h->X, v3);
1101   fe_mul(h->X, h->X, u); /* x = uv^3(uv^7)^((q-5)/8) */
1102
1103   fe_sq(vxx, h->X);
1104   fe_mul(vxx, vxx, v);
1105   fe_sub(check, vxx, u); /* vx^2-u */
1106   if (fe_isnonzero(check)) {
1107     fe_add(check, vxx, u); /* vx^2+u */
1108     if (fe_isnonzero(check)) {
1109       return -1;
1110     }
1111     fe_mul(h->X, h->X, sqrtm1);
1112   }
1113
1114   if (fe_isnegative(h->X) == (s[31] >> 7)) {
1115     fe_neg(h->X, h->X);
1116   }
1117
1118   fe_mul(h->T, h->X, h->Y);
1119   return 0;
1120 }
1121
1122 static void ge_p2_0(ge_p2 *h) {
1123   fe_0(h->X);
1124   fe_1(h->Y);
1125   fe_1(h->Z);
1126 }
1127
1128 static void ge_p3_0(ge_p3 *h) {
1129   fe_0(h->X);
1130   fe_1(h->Y);
1131   fe_1(h->Z);
1132   fe_0(h->T);
1133 }
1134
1135 static void ge_precomp_0(ge_precomp *h) {
1136   fe_1(h->yplusx);
1137   fe_1(h->yminusx);
1138   fe_0(h->xy2d);
1139 }
1140
1141 /* r = p */
1142 static void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) {
1143   fe_copy(r->X, p->X);
1144   fe_copy(r->Y, p->Y);
1145   fe_copy(r->Z, p->Z);
1146 }
1147
1148 static const fe d2 = {-21827239, -5839606,  -30745221, 13898782, 229458,
1149                       15978800,  -12551817, -6495438,  29715968, 9444199};
1150
1151 /* r = p */
1152 static void ge_p3_to_cached(ge_cached *r, const ge_p3 *p) {
1153   fe_add(r->YplusX, p->Y, p->X);
1154   fe_sub(r->YminusX, p->Y, p->X);
1155   fe_copy(r->Z, p->Z);
1156   fe_mul(r->T2d, p->T, d2);
1157 }
1158
1159 /* r = p */
1160 static void ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) {
1161   fe_mul(r->X, p->X, p->T);
1162   fe_mul(r->Y, p->Y, p->Z);
1163   fe_mul(r->Z, p->Z, p->T);
1164 }
1165
1166 /* r = p */
1167 static void ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) {
1168   fe_mul(r->X, p->X, p->T);
1169   fe_mul(r->Y, p->Y, p->Z);
1170   fe_mul(r->Z, p->Z, p->T);
1171   fe_mul(r->T, p->X, p->Y);
1172 }
1173
1174 /* r = 2 * p */
1175 static void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) {
1176   fe t0;
1177
1178   fe_sq(r->X, p->X);
1179   fe_sq(r->Z, p->Y);
1180   fe_sq2(r->T, p->Z);
1181   fe_add(r->Y, p->X, p->Y);
1182   fe_sq(t0, r->Y);
1183   fe_add(r->Y, r->Z, r->X);
1184   fe_sub(r->Z, r->Z, r->X);
1185   fe_sub(r->X, t0, r->Y);
1186   fe_sub(r->T, r->T, r->Z);
1187 }
1188
1189 /* r = 2 * p */
1190 static void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) {
1191   ge_p2 q;
1192   ge_p3_to_p2(&q, p);
1193   ge_p2_dbl(r, &q);
1194 }
1195
1196 /* r = p + q */
1197 static void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
1198   fe t0;
1199
1200   fe_add(r->X, p->Y, p->X);
1201   fe_sub(r->Y, p->Y, p->X);
1202   fe_mul(r->Z, r->X, q->yplusx);
1203   fe_mul(r->Y, r->Y, q->yminusx);
1204   fe_mul(r->T, q->xy2d, p->T);
1205   fe_add(t0, p->Z, p->Z);
1206   fe_sub(r->X, r->Z, r->Y);
1207   fe_add(r->Y, r->Z, r->Y);
1208   fe_add(r->Z, t0, r->T);
1209   fe_sub(r->T, t0, r->T);
1210 }
1211
1212 /* r = p - q */
1213 static void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
1214   fe t0;
1215
1216   fe_add(r->X, p->Y, p->X);
1217   fe_sub(r->Y, p->Y, p->X);
1218   fe_mul(r->Z, r->X, q->yminusx);
1219   fe_mul(r->Y, r->Y, q->yplusx);
1220   fe_mul(r->T, q->xy2d, p->T);
1221   fe_add(t0, p->Z, p->Z);
1222   fe_sub(r->X, r->Z, r->Y);
1223   fe_add(r->Y, r->Z, r->Y);
1224   fe_sub(r->Z, t0, r->T);
1225   fe_add(r->T, t0, r->T);
1226 }
1227
1228 /* r = p + q */
1229 static void ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
1230   fe t0;
1231
1232   fe_add(r->X, p->Y, p->X);
1233   fe_sub(r->Y, p->Y, p->X);
1234   fe_mul(r->Z, r->X, q->YplusX);
1235   fe_mul(r->Y, r->Y, q->YminusX);
1236   fe_mul(r->T, q->T2d, p->T);
1237   fe_mul(r->X, p->Z, q->Z);
1238   fe_add(t0, r->X, r->X);
1239   fe_sub(r->X, r->Z, r->Y);
1240   fe_add(r->Y, r->Z, r->Y);
1241   fe_add(r->Z, t0, r->T);
1242   fe_sub(r->T, t0, r->T);
1243 }
1244
1245 /* r = p - q */
1246 static void ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
1247   fe t0;
1248
1249   fe_add(r->X, p->Y, p->X);
1250   fe_sub(r->Y, p->Y, p->X);
1251   fe_mul(r->Z, r->X, q->YminusX);
1252   fe_mul(r->Y, r->Y, q->YplusX);
1253   fe_mul(r->T, q->T2d, p->T);
1254   fe_mul(r->X, p->Z, q->Z);
1255   fe_add(t0, r->X, r->X);
1256   fe_sub(r->X, r->Z, r->Y);
1257   fe_add(r->Y, r->Z, r->Y);
1258   fe_sub(r->Z, t0, r->T);
1259   fe_add(r->T, t0, r->T);
1260 }
1261
1262 static uint8_t equal(signed char b, signed char c) {
1263   uint8_t ub = b;
1264   uint8_t uc = c;
1265   uint8_t x = ub ^ uc; /* 0: yes; 1..255: no */
1266   uint32_t y = x;      /* 0: yes; 1..255: no */
1267   y -= 1;              /* 4294967295: yes; 0..254: no */
1268   y >>= 31;            /* 1: yes; 0: no */
1269   return y;
1270 }
1271
1272 static void cmov(ge_precomp *t, ge_precomp *u, uint8_t b) {
1273   fe_cmov(t->yplusx, u->yplusx, b);
1274   fe_cmov(t->yminusx, u->yminusx, b);
1275   fe_cmov(t->xy2d, u->xy2d, b);
1276 }
1277
1278 #if defined(OPENSSL_SMALL)
1279
1280 /* This block of code replaces the standard base-point table with a much smaller
1281  * one. The standard table is 30,720 bytes while this one is just 960.
1282  *
1283  * This table contains 15 pairs of group elements, (x, y), where each field
1284  * element is serialised with |fe_tobytes|. If |i| is the index of the group
1285  * element then consider i+1 as a four-bit number: (i₀, i₁, i₂, i₃) (where i₀
1286  * is the most significant bit). The value of the group element is then:
1287  * (i₀×2^192 + i₁×2^128 + i₂×2^64 + i₃)G, where G is the generator. */
1288 static const uint8_t k25519SmallPrecomp[15 * 2 * 32] = {
1289     0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, 0xb2, 0xa7, 0x25, 0x95,
1290     0x60, 0xc7, 0x2c, 0x69, 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
1291     0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21, 0x58, 0x66, 0x66, 0x66,
1292     0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
1293     0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
1294     0x66, 0x66, 0x66, 0x66, 0x02, 0xa2, 0xed, 0xf4, 0x8f, 0x6b, 0x0b, 0x3e,
1295     0xeb, 0x35, 0x1a, 0xd5, 0x7e, 0xdb, 0x78, 0x00, 0x96, 0x8a, 0xa0, 0xb4,
1296     0xcf, 0x60, 0x4b, 0xd4, 0xd5, 0xf9, 0x2d, 0xbf, 0x88, 0xbd, 0x22, 0x62,
1297     0x13, 0x53, 0xe4, 0x82, 0x57, 0xfa, 0x1e, 0x8f, 0x06, 0x2b, 0x90, 0xba,
1298     0x08, 0xb6, 0x10, 0x54, 0x4f, 0x7c, 0x1b, 0x26, 0xed, 0xda, 0x6b, 0xdd,
1299     0x25, 0xd0, 0x4e, 0xea, 0x42, 0xbb, 0x25, 0x03, 0xa2, 0xfb, 0xcc, 0x61,
1300     0x67, 0x06, 0x70, 0x1a, 0xc4, 0x78, 0x3a, 0xff, 0x32, 0x62, 0xdd, 0x2c,
1301     0xab, 0x50, 0x19, 0x3b, 0xf2, 0x9b, 0x7d, 0xb8, 0xfd, 0x4f, 0x29, 0x9c,
1302     0xa7, 0x91, 0xba, 0x0e, 0x46, 0x5e, 0x51, 0xfe, 0x1d, 0xbf, 0xe5, 0xe5,
1303     0x9b, 0x95, 0x0d, 0x67, 0xf8, 0xd1, 0xb5, 0x5a, 0xa1, 0x93, 0x2c, 0xc3,
1304     0xde, 0x0e, 0x97, 0x85, 0x2d, 0x7f, 0xea, 0xab, 0x3e, 0x47, 0x30, 0x18,
1305     0x24, 0xe8, 0xb7, 0x60, 0xae, 0x47, 0x80, 0xfc, 0xe5, 0x23, 0xe7, 0xc2,
1306     0xc9, 0x85, 0xe6, 0x98, 0xa0, 0x29, 0x4e, 0xe1, 0x84, 0x39, 0x2d, 0x95,
1307     0x2c, 0xf3, 0x45, 0x3c, 0xff, 0xaf, 0x27, 0x4c, 0x6b, 0xa6, 0xf5, 0x4b,
1308     0x11, 0xbd, 0xba, 0x5b, 0x9e, 0xc4, 0xa4, 0x51, 0x1e, 0xbe, 0xd0, 0x90,
1309     0x3a, 0x9c, 0xc2, 0x26, 0xb6, 0x1e, 0xf1, 0x95, 0x7d, 0xc8, 0x6d, 0x52,
1310     0xe6, 0x99, 0x2c, 0x5f, 0x9a, 0x96, 0x0c, 0x68, 0x29, 0xfd, 0xe2, 0xfb,
1311     0xe6, 0xbc, 0xec, 0x31, 0x08, 0xec, 0xe6, 0xb0, 0x53, 0x60, 0xc3, 0x8c,
1312     0xbe, 0xc1, 0xb3, 0x8a, 0x8f, 0xe4, 0x88, 0x2b, 0x55, 0xe5, 0x64, 0x6e,
1313     0x9b, 0xd0, 0xaf, 0x7b, 0x64, 0x2a, 0x35, 0x25, 0x10, 0x52, 0xc5, 0x9e,
1314     0x58, 0x11, 0x39, 0x36, 0x45, 0x51, 0xb8, 0x39, 0x93, 0xfc, 0x9d, 0x6a,
1315     0xbe, 0x58, 0xcb, 0xa4, 0x0f, 0x51, 0x3c, 0x38, 0x05, 0xca, 0xab, 0x43,
1316     0x63, 0x0e, 0xf3, 0x8b, 0x41, 0xa6, 0xf8, 0x9b, 0x53, 0x70, 0x80, 0x53,
1317     0x86, 0x5e, 0x8f, 0xe3, 0xc3, 0x0d, 0x18, 0xc8, 0x4b, 0x34, 0x1f, 0xd8,
1318     0x1d, 0xbc, 0xf2, 0x6d, 0x34, 0x3a, 0xbe, 0xdf, 0xd9, 0xf6, 0xf3, 0x89,
1319     0xa1, 0xe1, 0x94, 0x9f, 0x5d, 0x4c, 0x5d, 0xe9, 0xa1, 0x49, 0x92, 0xef,
1320     0x0e, 0x53, 0x81, 0x89, 0x58, 0x87, 0xa6, 0x37, 0xf1, 0xdd, 0x62, 0x60,
1321     0x63, 0x5a, 0x9d, 0x1b, 0x8c, 0xc6, 0x7d, 0x52, 0xea, 0x70, 0x09, 0x6a,
1322     0xe1, 0x32, 0xf3, 0x73, 0x21, 0x1f, 0x07, 0x7b, 0x7c, 0x9b, 0x49, 0xd8,
1323     0xc0, 0xf3, 0x25, 0x72, 0x6f, 0x9d, 0xed, 0x31, 0x67, 0x36, 0x36, 0x54,
1324     0x40, 0x92, 0x71, 0xe6, 0x11, 0x28, 0x11, 0xad, 0x93, 0x32, 0x85, 0x7b,
1325     0x3e, 0xb7, 0x3b, 0x49, 0x13, 0x1c, 0x07, 0xb0, 0x2e, 0x93, 0xaa, 0xfd,
1326     0xfd, 0x28, 0x47, 0x3d, 0x8d, 0xd2, 0xda, 0xc7, 0x44, 0xd6, 0x7a, 0xdb,
1327     0x26, 0x7d, 0x1d, 0xb8, 0xe1, 0xde, 0x9d, 0x7a, 0x7d, 0x17, 0x7e, 0x1c,
1328     0x37, 0x04, 0x8d, 0x2d, 0x7c, 0x5e, 0x18, 0x38, 0x1e, 0xaf, 0xc7, 0x1b,
1329     0x33, 0x48, 0x31, 0x00, 0x59, 0xf6, 0xf2, 0xca, 0x0f, 0x27, 0x1b, 0x63,
1330     0x12, 0x7e, 0x02, 0x1d, 0x49, 0xc0, 0x5d, 0x79, 0x87, 0xef, 0x5e, 0x7a,
1331     0x2f, 0x1f, 0x66, 0x55, 0xd8, 0x09, 0xd9, 0x61, 0x38, 0x68, 0xb0, 0x07,
1332     0xa3, 0xfc, 0xcc, 0x85, 0x10, 0x7f, 0x4c, 0x65, 0x65, 0xb3, 0xfa, 0xfa,
1333     0xa5, 0x53, 0x6f, 0xdb, 0x74, 0x4c, 0x56, 0x46, 0x03, 0xe2, 0xd5, 0x7a,
1334     0x29, 0x1c, 0xc6, 0x02, 0xbc, 0x59, 0xf2, 0x04, 0x75, 0x63, 0xc0, 0x84,
1335     0x2f, 0x60, 0x1c, 0x67, 0x76, 0xfd, 0x63, 0x86, 0xf3, 0xfa, 0xbf, 0xdc,
1336     0xd2, 0x2d, 0x90, 0x91, 0xbd, 0x33, 0xa9, 0xe5, 0x66, 0x0c, 0xda, 0x42,
1337     0x27, 0xca, 0xf4, 0x66, 0xc2, 0xec, 0x92, 0x14, 0x57, 0x06, 0x63, 0xd0,
1338     0x4d, 0x15, 0x06, 0xeb, 0x69, 0x58, 0x4f, 0x77, 0xc5, 0x8b, 0xc7, 0xf0,
1339     0x8e, 0xed, 0x64, 0xa0, 0xb3, 0x3c, 0x66, 0x71, 0xc6, 0x2d, 0xda, 0x0a,
1340     0x0d, 0xfe, 0x70, 0x27, 0x64, 0xf8, 0x27, 0xfa, 0xf6, 0x5f, 0x30, 0xa5,
1341     0x0d, 0x6c, 0xda, 0xf2, 0x62, 0x5e, 0x78, 0x47, 0xd3, 0x66, 0x00, 0x1c,
1342     0xfd, 0x56, 0x1f, 0x5d, 0x3f, 0x6f, 0xf4, 0x4c, 0xd8, 0xfd, 0x0e, 0x27,
1343     0xc9, 0x5c, 0x2b, 0xbc, 0xc0, 0xa4, 0xe7, 0x23, 0x29, 0x02, 0x9f, 0x31,
1344     0xd6, 0xe9, 0xd7, 0x96, 0xf4, 0xe0, 0x5e, 0x0b, 0x0e, 0x13, 0xee, 0x3c,
1345     0x09, 0xed, 0xf2, 0x3d, 0x76, 0x91, 0xc3, 0xa4, 0x97, 0xae, 0xd4, 0x87,
1346     0xd0, 0x5d, 0xf6, 0x18, 0x47, 0x1f, 0x1d, 0x67, 0xf2, 0xcf, 0x63, 0xa0,
1347     0x91, 0x27, 0xf8, 0x93, 0x45, 0x75, 0x23, 0x3f, 0xd1, 0xf1, 0xad, 0x23,
1348     0xdd, 0x64, 0x93, 0x96, 0x41, 0x70, 0x7f, 0xf7, 0xf5, 0xa9, 0x89, 0xa2,
1349     0x34, 0xb0, 0x8d, 0x1b, 0xae, 0x19, 0x15, 0x49, 0x58, 0x23, 0x6d, 0x87,
1350     0x15, 0x4f, 0x81, 0x76, 0xfb, 0x23, 0xb5, 0xea, 0xcf, 0xac, 0x54, 0x8d,
1351     0x4e, 0x42, 0x2f, 0xeb, 0x0f, 0x63, 0xdb, 0x68, 0x37, 0xa8, 0xcf, 0x8b,
1352     0xab, 0xf5, 0xa4, 0x6e, 0x96, 0x2a, 0xb2, 0xd6, 0xbe, 0x9e, 0xbd, 0x0d,
1353     0xb4, 0x42, 0xa9, 0xcf, 0x01, 0x83, 0x8a, 0x17, 0x47, 0x76, 0xc4, 0xc6,
1354     0x83, 0x04, 0x95, 0x0b, 0xfc, 0x11, 0xc9, 0x62, 0xb8, 0x0c, 0x76, 0x84,
1355     0xd9, 0xb9, 0x37, 0xfa, 0xfc, 0x7c, 0xc2, 0x6d, 0x58, 0x3e, 0xb3, 0x04,
1356     0xbb, 0x8c, 0x8f, 0x48, 0xbc, 0x91, 0x27, 0xcc, 0xf9, 0xb7, 0x22, 0x19,
1357     0x83, 0x2e, 0x09, 0xb5, 0x72, 0xd9, 0x54, 0x1c, 0x4d, 0xa1, 0xea, 0x0b,
1358     0xf1, 0xc6, 0x08, 0x72, 0x46, 0x87, 0x7a, 0x6e, 0x80, 0x56, 0x0a, 0x8a,
1359     0xc0, 0xdd, 0x11, 0x6b, 0xd6, 0xdd, 0x47, 0xdf, 0x10, 0xd9, 0xd8, 0xea,
1360     0x7c, 0xb0, 0x8f, 0x03, 0x00, 0x2e, 0xc1, 0x8f, 0x44, 0xa8, 0xd3, 0x30,
1361     0x06, 0x89, 0xa2, 0xf9, 0x34, 0xad, 0xdc, 0x03, 0x85, 0xed, 0x51, 0xa7,
1362     0x82, 0x9c, 0xe7, 0x5d, 0x52, 0x93, 0x0c, 0x32, 0x9a, 0x5b, 0xe1, 0xaa,
1363     0xca, 0xb8, 0x02, 0x6d, 0x3a, 0xd4, 0xb1, 0x3a, 0xf0, 0x5f, 0xbe, 0xb5,
1364     0x0d, 0x10, 0x6b, 0x38, 0x32, 0xac, 0x76, 0x80, 0xbd, 0xca, 0x94, 0x71,
1365     0x7a, 0xf2, 0xc9, 0x35, 0x2a, 0xde, 0x9f, 0x42, 0x49, 0x18, 0x01, 0xab,
1366     0xbc, 0xef, 0x7c, 0x64, 0x3f, 0x58, 0x3d, 0x92, 0x59, 0xdb, 0x13, 0xdb,
1367     0x58, 0x6e, 0x0a, 0xe0, 0xb7, 0x91, 0x4a, 0x08, 0x20, 0xd6, 0x2e, 0x3c,
1368     0x45, 0xc9, 0x8b, 0x17, 0x79, 0xe7, 0xc7, 0x90, 0x99, 0x3a, 0x18, 0x25,
1369 };
1370
1371 static void ge_scalarmult_base(ge_p3 *h, const uint8_t a[32]) {
1372   /* k25519SmallPrecomp is first expanded into matching |ge_precomp|
1373    * elements. */
1374   ge_precomp multiples[15];
1375
1376   unsigned i;
1377   for (i = 0; i < 15; i++) {
1378     const uint8_t *bytes = &k25519SmallPrecomp[i*(2 * 32)];
1379     fe x, y;
1380     fe_frombytes(x, bytes);
1381     fe_frombytes(y, bytes + 32);
1382
1383     ge_precomp *out = &multiples[i];
1384     fe_add(out->yplusx, y, x);
1385     fe_sub(out->yminusx, y, x);
1386     fe_mul(out->xy2d, x, y);
1387     fe_mul(out->xy2d, out->xy2d, d2);
1388   }
1389
1390   /* See the comment above |k25519SmallPrecomp| about the structure of the
1391    * precomputed elements. This loop does 64 additions and 64 doublings to
1392    * calculate the result. */
1393   ge_p3_0(h);
1394
1395   for (i = 63; i < 64; i--) {
1396     unsigned j;
1397     signed char index = 0;
1398
1399     for (j = 0; j < 4; j++) {
1400       const uint8_t bit = 1 & (a[(8 * j) + (i / 8)] >> (i & 7));
1401       index |= (bit << j);
1402     }
1403
1404     ge_precomp e;
1405     ge_precomp_0(&e);
1406
1407     for (j = 1; j < 16; j++) {
1408       cmov(&e, &multiples[j-1], equal(index, j));
1409     }
1410
1411     ge_cached cached;
1412     ge_p1p1 r;
1413     ge_p3_to_cached(&cached, h);
1414     ge_add(&r, h, &cached);
1415     ge_p1p1_to_p3(h, &r);
1416
1417     ge_madd(&r, h, &e);
1418     ge_p1p1_to_p3(h, &r);
1419   }
1420 }
1421
1422 #else
1423
1424 /* k25519Precomp[i][j] = (j+1)*256^i*B */
1425 static ge_precomp k25519Precomp[32][8] = {
1426     {
1427         {
1428             {25967493, -14356035, 29566456, 3660896, -12694345, 4014787,
1429              27544626, -11754271, -6079156, 2047605},
1430             {-12545711, 934262, -2722910, 3049990, -727428, 9406986, 12720692,
1431              5043384, 19500929, -15469378},
1432             {-8738181, 4489570, 9688441, -14785194, 10184609, -12363380,
1433              29287919, 11864899, -24514362, -4438546},
1434         },
1435         {
1436             {-12815894, -12976347, -21581243, 11784320, -25355658, -2750717,
1437              -11717903, -3814571, -358445, -10211303},
1438             {-21703237, 6903825, 27185491, 6451973, -29577724, -9554005,
1439              -15616551, 11189268, -26829678, -5319081},
1440             {26966642, 11152617, 32442495, 15396054, 14353839, -12752335,
1441              -3128826, -9541118, -15472047, -4166697},
1442         },
1443         {
1444             {15636291, -9688557, 24204773, -7912398, 616977, -16685262,
1445              27787600, -14772189, 28944400, -1550024},
1446             {16568933, 4717097, -11556148, -1102322, 15682896, -11807043,
1447              16354577, -11775962, 7689662, 11199574},
1448             {30464156, -5976125, -11779434, -15670865, 23220365, 15915852,
1449              7512774, 10017326, -17749093, -9920357},
1450         },
1451         {
1452             {-17036878, 13921892, 10945806, -6033431, 27105052, -16084379,
1453              -28926210, 15006023, 3284568, -6276540},
1454             {23599295, -8306047, -11193664, -7687416, 13236774, 10506355,
1455              7464579, 9656445, 13059162, 10374397},
1456             {7798556, 16710257, 3033922, 2874086, 28997861, 2835604, 32406664,
1457              -3839045, -641708, -101325},
1458         },
1459         {
1460             {10861363, 11473154, 27284546, 1981175, -30064349, 12577861,
1461              32867885, 14515107, -15438304, 10819380},
1462             {4708026, 6336745, 20377586, 9066809, -11272109, 6594696, -25653668,
1463              12483688, -12668491, 5581306},
1464             {19563160, 16186464, -29386857, 4097519, 10237984, -4348115,
1465              28542350, 13850243, -23678021, -15815942},
1466         },
1467         {
1468             {-15371964, -12862754, 32573250, 4720197, -26436522, 5875511,
1469              -19188627, -15224819, -9818940, -12085777},
1470             {-8549212, 109983, 15149363, 2178705, 22900618, 4543417, 3044240,
1471              -15689887, 1762328, 14866737},
1472             {-18199695, -15951423, -10473290, 1707278, -17185920, 3916101,
1473              -28236412, 3959421, 27914454, 4383652},
1474         },
1475         {
1476             {5153746, 9909285, 1723747, -2777874, 30523605, 5516873, 19480852,
1477              5230134, -23952439, -15175766},
1478             {-30269007, -3463509, 7665486, 10083793, 28475525, 1649722,
1479              20654025, 16520125, 30598449, 7715701},
1480             {28881845, 14381568, 9657904, 3680757, -20181635, 7843316,
1481              -31400660, 1370708, 29794553, -1409300},
1482         },
1483         {
1484             {14499471, -2729599, -33191113, -4254652, 28494862, 14271267,
1485              30290735, 10876454, -33154098, 2381726},
1486             {-7195431, -2655363, -14730155, 462251, -27724326, 3941372,
1487              -6236617, 3696005, -32300832, 15351955},
1488             {27431194, 8222322, 16448760, -3907995, -18707002, 11938355,
1489              -32961401, -2970515, 29551813, 10109425},
1490         },
1491     },
1492     {
1493         {
1494             {-13657040, -13155431, -31283750, 11777098, 21447386, 6519384,
1495              -2378284, -1627556, 10092783, -4764171},
1496             {27939166, 14210322, 4677035, 16277044, -22964462, -12398139,
1497              -32508754, 12005538, -17810127, 12803510},
1498             {17228999, -15661624, -1233527, 300140, -1224870, -11714777,
1499              30364213, -9038194, 18016357, 4397660},
1500         },
1501         {
1502             {-10958843, -7690207, 4776341, -14954238, 27850028, -15602212,
1503              -26619106, 14544525, -17477504, 982639},
1504             {29253598, 15796703, -2863982, -9908884, 10057023, 3163536, 7332899,
1505              -4120128, -21047696, 9934963},
1506             {5793303, 16271923, -24131614, -10116404, 29188560, 1206517,
1507              -14747930, 4559895, -30123922, -10897950},
1508         },
1509         {
1510             {-27643952, -11493006, 16282657, -11036493, 28414021, -15012264,
1511              24191034, 4541697, -13338309, 5500568},
1512             {12650548, -1497113, 9052871, 11355358, -17680037, -8400164,
1513              -17430592, 12264343, 10874051, 13524335},
1514             {25556948, -3045990, 714651, 2510400, 23394682, -10415330, 33119038,
1515              5080568, -22528059, 5376628},
1516         },
1517         {
1518             {-26088264, -4011052, -17013699, -3537628, -6726793, 1920897,
1519              -22321305, -9447443, 4535768, 1569007},
1520             {-2255422, 14606630, -21692440, -8039818, 28430649, 8775819,
1521              -30494562, 3044290, 31848280, 12543772},
1522             {-22028579, 2943893, -31857513, 6777306, 13784462, -4292203,
1523              -27377195, -2062731, 7718482, 14474653},
1524         },
1525         {
1526             {2385315, 2454213, -22631320, 46603, -4437935, -15680415, 656965,
1527              -7236665, 24316168, -5253567},
1528             {13741529, 10911568, -33233417, -8603737, -20177830, -1033297,
1529              33040651, -13424532, -20729456, 8321686},
1530             {21060490, -2212744, 15712757, -4336099, 1639040, 10656336,
1531              23845965, -11874838, -9984458, 608372},
1532         },
1533         {
1534             {-13672732, -15087586, -10889693, -7557059, -6036909, 11305547,
1535              1123968, -6780577, 27229399, 23887},
1536             {-23244140, -294205, -11744728, 14712571, -29465699, -2029617,
1537              12797024, -6440308, -1633405, 16678954},
1538             {-29500620, 4770662, -16054387, 14001338, 7830047, 9564805,
1539              -1508144, -4795045, -17169265, 4904953},
1540         },
1541         {
1542             {24059557, 14617003, 19037157, -15039908, 19766093, -14906429,
1543              5169211, 16191880, 2128236, -4326833},
1544             {-16981152, 4124966, -8540610, -10653797, 30336522, -14105247,
1545              -29806336, 916033, -6882542, -2986532},
1546             {-22630907, 12419372, -7134229, -7473371, -16478904, 16739175,
1547              285431, 2763829, 15736322, 4143876},
1548         },
1549         {
1550             {2379352, 11839345, -4110402, -5988665, 11274298, 794957, 212801,
1551              -14594663, 23527084, -16458268},
1552             {33431127, -11130478, -17838966, -15626900, 8909499, 8376530,
1553              -32625340, 4087881, -15188911, -14416214},
1554             {1767683, 7197987, -13205226, -2022635, -13091350, 448826, 5799055,
1555              4357868, -4774191, -16323038},
1556         },
1557     },
1558     {
1559         {
1560             {6721966, 13833823, -23523388, -1551314, 26354293, -11863321,
1561              23365147, -3949732, 7390890, 2759800},
1562             {4409041, 2052381, 23373853, 10530217, 7676779, -12885954, 21302353,
1563              -4264057, 1244380, -12919645},
1564             {-4421239, 7169619, 4982368, -2957590, 30256825, -2777540, 14086413,
1565              9208236, 15886429, 16489664},
1566         },
1567         {
1568             {1996075, 10375649, 14346367, 13311202, -6874135, -16438411,
1569              -13693198, 398369, -30606455, -712933},
1570             {-25307465, 9795880, -2777414, 14878809, -33531835, 14780363,
1571              13348553, 12076947, -30836462, 5113182},
1572             {-17770784, 11797796, 31950843, 13929123, -25888302, 12288344,
1573              -30341101, -7336386, 13847711, 5387222},
1574         },
1575         {
1576             {-18582163, -3416217, 17824843, -2340966, 22744343, -10442611,
1577              8763061, 3617786, -19600662, 10370991},
1578             {20246567, -14369378, 22358229, -543712, 18507283, -10413996,
1579              14554437, -8746092, 32232924, 16763880},
1580             {9648505, 10094563, 26416693, 14745928, -30374318, -6472621,
1581              11094161, 15689506, 3140038, -16510092},
1582         },
1583         {
1584             {-16160072, 5472695, 31895588, 4744994, 8823515, 10365685,
1585              -27224800, 9448613, -28774454, 366295},
1586             {19153450, 11523972, -11096490, -6503142, -24647631, 5420647,
1587              28344573, 8041113, 719605, 11671788},
1588             {8678025, 2694440, -6808014, 2517372, 4964326, 11152271, -15432916,
1589              -15266516, 27000813, -10195553},
1590         },
1591         {
1592             {-15157904, 7134312, 8639287, -2814877, -7235688, 10421742, 564065,
1593              5336097, 6750977, -14521026},
1594             {11836410, -3979488, 26297894, 16080799, 23455045, 15735944,
1595              1695823, -8819122, 8169720, 16220347},
1596             {-18115838, 8653647, 17578566, -6092619, -8025777, -16012763,
1597              -11144307, -2627664, -5990708, -14166033},
1598         },
1599         {
1600             {-23308498, -10968312, 15213228, -10081214, -30853605, -11050004,
1601              27884329, 2847284, 2655861, 1738395},
1602             {-27537433, -14253021, -25336301, -8002780, -9370762, 8129821,
1603              21651608, -3239336, -19087449, -11005278},
1604             {1533110, 3437855, 23735889, 459276, 29970501, 11335377, 26030092,
1605              5821408, 10478196, 8544890},
1606         },
1607         {
1608             {32173121, -16129311, 24896207, 3921497, 22579056, -3410854,
1609              19270449, 12217473, 17789017, -3395995},
1610             {-30552961, -2228401, -15578829, -10147201, 13243889, 517024,
1611              15479401, -3853233, 30460520, 1052596},
1612             {-11614875, 13323618, 32618793, 8175907, -15230173, 12596687,
1613              27491595, -4612359, 3179268, -9478891},
1614         },
1615         {
1616             {31947069, -14366651, -4640583, -15339921, -15125977, -6039709,
1617              -14756777, -16411740, 19072640, -9511060},
1618             {11685058, 11822410, 3158003, -13952594, 33402194, -4165066,
1619              5977896, -5215017, 473099, 5040608},
1620             {-20290863, 8198642, -27410132, 11602123, 1290375, -2799760,
1621              28326862, 1721092, -19558642, -3131606},
1622         },
1623     },
1624     {
1625         {
1626             {7881532, 10687937, 7578723, 7738378, -18951012, -2553952, 21820786,
1627              8076149, -27868496, 11538389},
1628             {-19935666, 3899861, 18283497, -6801568, -15728660, -11249211,
1629              8754525, 7446702, -5676054, 5797016},
1630             {-11295600, -3793569, -15782110, -7964573, 12708869, -8456199,
1631              2014099, -9050574, -2369172, -5877341},
1632         },
1633         {
1634             {-22472376, -11568741, -27682020, 1146375, 18956691, 16640559,
1635              1192730, -3714199, 15123619, 10811505},
1636             {14352098, -3419715, -18942044, 10822655, 32750596, 4699007, -70363,
1637              15776356, -28886779, -11974553},
1638             {-28241164, -8072475, -4978962, -5315317, 29416931, 1847569,
1639              -20654173, -16484855, 4714547, -9600655},
1640         },
1641         {
1642             {15200332, 8368572, 19679101, 15970074, -31872674, 1959451,
1643              24611599, -4543832, -11745876, 12340220},
1644             {12876937, -10480056, 33134381, 6590940, -6307776, 14872440,
1645              9613953, 8241152, 15370987, 9608631},
1646             {-4143277, -12014408, 8446281, -391603, 4407738, 13629032, -7724868,
1647              15866074, -28210621, -8814099},
1648         },
1649         {
1650             {26660628, -15677655, 8393734, 358047, -7401291, 992988, -23904233,
1651              858697, 20571223, 8420556},
1652             {14620715, 13067227, -15447274, 8264467, 14106269, 15080814,
1653              33531827, 12516406, -21574435, -12476749},
1654             {236881, 10476226, 57258, -14677024, 6472998, 2466984, 17258519,
1655              7256740, 8791136, 15069930},
1656         },
1657         {
1658             {1276410, -9371918, 22949635, -16322807, -23493039, -5702186,
1659              14711875, 4874229, -30663140, -2331391},
1660             {5855666, 4990204, -13711848, 7294284, -7804282, 1924647, -1423175,
1661              -7912378, -33069337, 9234253},
1662             {20590503, -9018988, 31529744, -7352666, -2706834, 10650548,
1663              31559055, -11609587, 18979186, 13396066},
1664         },
1665         {
1666             {24474287, 4968103, 22267082, 4407354, 24063882, -8325180,
1667              -18816887, 13594782, 33514650, 7021958},
1668             {-11566906, -6565505, -21365085, 15928892, -26158305, 4315421,
1669              -25948728, -3916677, -21480480, 12868082},
1670             {-28635013, 13504661, 19988037, -2132761, 21078225, 6443208,
1671              -21446107, 2244500, -12455797, -8089383},
1672         },
1673         {
1674             {-30595528, 13793479, -5852820, 319136, -25723172, -6263899,
1675              33086546, 8957937, -15233648, 5540521},
1676             {-11630176, -11503902, -8119500, -7643073, 2620056, 1022908,
1677              -23710744, -1568984, -16128528, -14962807},
1678             {23152971, 775386, 27395463, 14006635, -9701118, 4649512, 1689819,
1679              892185, -11513277, -15205948},
1680         },
1681         {
1682             {9770129, 9586738, 26496094, 4324120, 1556511, -3550024, 27453819,
1683              4763127, -19179614, 5867134},
1684             {-32765025, 1927590, 31726409, -4753295, 23962434, -16019500,
1685              27846559, 5931263, -29749703, -16108455},
1686             {27461885, -2977536, 22380810, 1815854, -23033753, -3031938,
1687              7283490, -15148073, -19526700, 7734629},
1688         },
1689     },
1690     {
1691         {
1692             {-8010264, -9590817, -11120403, 6196038, 29344158, -13430885,
1693              7585295, -3176626, 18549497, 15302069},
1694             {-32658337, -6171222, -7672793, -11051681, 6258878, 13504381,
1695              10458790, -6418461, -8872242, 8424746},
1696             {24687205, 8613276, -30667046, -3233545, 1863892, -1830544,
1697              19206234, 7134917, -11284482, -828919},
1698         },
1699         {
1700             {11334899, -9218022, 8025293, 12707519, 17523892, -10476071,
1701              10243738, -14685461, -5066034, 16498837},
1702             {8911542, 6887158, -9584260, -6958590, 11145641, -9543680, 17303925,
1703              -14124238, 6536641, 10543906},
1704             {-28946384, 15479763, -17466835, 568876, -1497683, 11223454,
1705              -2669190, -16625574, -27235709, 8876771},
1706         },
1707         {
1708             {-25742899, -12566864, -15649966, -846607, -33026686, -796288,
1709              -33481822, 15824474, -604426, -9039817},
1710             {10330056, 70051, 7957388, -9002667, 9764902, 15609756, 27698697,
1711              -4890037, 1657394, 3084098},
1712             {10477963, -7470260, 12119566, -13250805, 29016247, -5365589,
1713              31280319, 14396151, -30233575, 15272409},
1714         },
1715         {
1716             {-12288309, 3169463, 28813183, 16658753, 25116432, -5630466,
1717              -25173957, -12636138, -25014757, 1950504},
1718             {-26180358, 9489187, 11053416, -14746161, -31053720, 5825630,
1719              -8384306, -8767532, 15341279, 8373727},
1720             {28685821, 7759505, -14378516, -12002860, -31971820, 4079242,
1721              298136, -10232602, -2878207, 15190420},
1722         },
1723         {
1724             {-32932876, 13806336, -14337485, -15794431, -24004620, 10940928,
1725              8669718, 2742393, -26033313, -6875003},
1726             {-1580388, -11729417, -25979658, -11445023, -17411874, -10912854,
1727              9291594, -16247779, -12154742, 6048605},
1728             {-30305315, 14843444, 1539301, 11864366, 20201677, 1900163,
1729              13934231, 5128323, 11213262, 9168384},
1730         },
1731         {
1732             {-26280513, 11007847, 19408960, -940758, -18592965, -4328580,
1733              -5088060, -11105150, 20470157, -16398701},
1734             {-23136053, 9282192, 14855179, -15390078, -7362815, -14408560,
1735              -22783952, 14461608, 14042978, 5230683},
1736             {29969567, -2741594, -16711867, -8552442, 9175486, -2468974,
1737              21556951, 3506042, -5933891, -12449708},
1738         },
1739         {
1740             {-3144746, 8744661, 19704003, 4581278, -20430686, 6830683,
1741              -21284170, 8971513, -28539189, 15326563},
1742             {-19464629, 10110288, -17262528, -3503892, -23500387, 1355669,
1743              -15523050, 15300988, -20514118, 9168260},
1744             {-5353335, 4488613, -23803248, 16314347, 7780487, -15638939,
1745              -28948358, 9601605, 33087103, -9011387},
1746         },
1747         {
1748             {-19443170, -15512900, -20797467, -12445323, -29824447, 10229461,
1749              -27444329, -15000531, -5996870, 15664672},
1750             {23294591, -16632613, -22650781, -8470978, 27844204, 11461195,
1751              13099750, -2460356, 18151676, 13417686},
1752             {-24722913, -4176517, -31150679, 5988919, -26858785, 6685065,
1753              1661597, -12551441, 15271676, -15452665},
1754         },
1755     },
1756     {
1757         {
1758             {11433042, -13228665, 8239631, -5279517, -1985436, -725718,
1759              -18698764, 2167544, -6921301, -13440182},
1760             {-31436171, 15575146, 30436815, 12192228, -22463353, 9395379,
1761              -9917708, -8638997, 12215110, 12028277},
1762             {14098400, 6555944, 23007258, 5757252, -15427832, -12950502,
1763              30123440, 4617780, -16900089, -655628},
1764         },
1765         {
1766             {-4026201, -15240835, 11893168, 13718664, -14809462, 1847385,
1767              -15819999, 10154009, 23973261, -12684474},
1768             {-26531820, -3695990, -1908898, 2534301, -31870557, -16550355,
1769              18341390, -11419951, 32013174, -10103539},
1770             {-25479301, 10876443, -11771086, -14625140, -12369567, 1838104,
1771              21911214, 6354752, 4425632, -837822},
1772         },
1773         {
1774             {-10433389, -14612966, 22229858, -3091047, -13191166, 776729,
1775              -17415375, -12020462, 4725005, 14044970},
1776             {19268650, -7304421, 1555349, 8692754, -21474059, -9910664, 6347390,
1777              -1411784, -19522291, -16109756},
1778             {-24864089, 12986008, -10898878, -5558584, -11312371, -148526,
1779              19541418, 8180106, 9282262, 10282508},
1780         },
1781         {
1782             {-26205082, 4428547, -8661196, -13194263, 4098402, -14165257,
1783              15522535, 8372215, 5542595, -10702683},
1784             {-10562541, 14895633, 26814552, -16673850, -17480754, -2489360,
1785              -2781891, 6993761, -18093885, 10114655},
1786             {-20107055, -929418, 31422704, 10427861, -7110749, 6150669,
1787              -29091755, -11529146, 25953725, -106158},
1788         },
1789         {
1790             {-4234397, -8039292, -9119125, 3046000, 2101609, -12607294,
1791              19390020, 6094296, -3315279, 12831125},
1792             {-15998678, 7578152, 5310217, 14408357, -33548620, -224739,
1793              31575954, 6326196, 7381791, -2421839},
1794             {-20902779, 3296811, 24736065, -16328389, 18374254, 7318640,
1795              6295303, 8082724, -15362489, 12339664},
1796         },
1797         {
1798             {27724736, 2291157, 6088201, -14184798, 1792727, 5857634, 13848414,
1799              15768922, 25091167, 14856294},
1800             {-18866652, 8331043, 24373479, 8541013, -701998, -9269457, 12927300,
1801              -12695493, -22182473, -9012899},
1802             {-11423429, -5421590, 11632845, 3405020, 30536730, -11674039,
1803              -27260765, 13866390, 30146206, 9142070},
1804         },
1805         {
1806             {3924129, -15307516, -13817122, -10054960, 12291820, -668366,
1807              -27702774, 9326384, -8237858, 4171294},
1808             {-15921940, 16037937, 6713787, 16606682, -21612135, 2790944,
1809              26396185, 3731949, 345228, -5462949},
1810             {-21327538, 13448259, 25284571, 1143661, 20614966, -8849387,
1811              2031539, -12391231, -16253183, -13582083},
1812         },
1813         {
1814             {31016211, -16722429, 26371392, -14451233, -5027349, 14854137,
1815              17477601, 3842657, 28012650, -16405420},
1816             {-5075835, 9368966, -8562079, -4600902, -15249953, 6970560,
1817              -9189873, 16292057, -8867157, 3507940},
1818             {29439664, 3537914, 23333589, 6997794, -17555561, -11018068,
1819              -15209202, -15051267, -9164929, 6580396},
1820         },
1821     },
1822     {
1823         {
1824             {-12185861, -7679788, 16438269, 10826160, -8696817, -6235611,
1825              17860444, -9273846, -2095802, 9304567},
1826             {20714564, -4336911, 29088195, 7406487, 11426967, -5095705,
1827              14792667, -14608617, 5289421, -477127},
1828             {-16665533, -10650790, -6160345, -13305760, 9192020, -1802462,
1829              17271490, 12349094, 26939669, -3752294},
1830         },
1831         {
1832             {-12889898, 9373458, 31595848, 16374215, 21471720, 13221525,
1833              -27283495, -12348559, -3698806, 117887},
1834             {22263325, -6560050, 3984570, -11174646, -15114008, -566785,
1835              28311253, 5358056, -23319780, 541964},
1836             {16259219, 3261970, 2309254, -15534474, -16885711, -4581916,
1837              24134070, -16705829, -13337066, -13552195},
1838         },
1839         {
1840             {9378160, -13140186, -22845982, -12745264, 28198281, -7244098,
1841              -2399684, -717351, 690426, 14876244},
1842             {24977353, -314384, -8223969, -13465086, 28432343, -1176353,
1843              -13068804, -12297348, -22380984, 6618999},
1844             {-1538174, 11685646, 12944378, 13682314, -24389511, -14413193,
1845              8044829, -13817328, 32239829, -5652762},
1846         },
1847         {
1848             {-18603066, 4762990, -926250, 8885304, -28412480, -3187315, 9781647,
1849              -10350059, 32779359, 5095274},
1850             {-33008130, -5214506, -32264887, -3685216, 9460461, -9327423,
1851              -24601656, 14506724, 21639561, -2630236},
1852             {-16400943, -13112215, 25239338, 15531969, 3987758, -4499318,
1853              -1289502, -6863535, 17874574, 558605},
1854         },
1855         {
1856             {-13600129, 10240081, 9171883, 16131053, -20869254, 9599700,
1857              33499487, 5080151, 2085892, 5119761},
1858             {-22205145, -2519528, -16381601, 414691, -25019550, 2170430,
1859              30634760, -8363614, -31999993, -5759884},
1860             {-6845704, 15791202, 8550074, -1312654, 29928809, -12092256,
1861              27534430, -7192145, -22351378, 12961482},
1862         },
1863         {
1864             {-24492060, -9570771, 10368194, 11582341, -23397293, -2245287,
1865              16533930, 8206996, -30194652, -5159638},
1866             {-11121496, -3382234, 2307366, 6362031, -135455, 8868177, -16835630,
1867              7031275, 7589640, 8945490},
1868             {-32152748, 8917967, 6661220, -11677616, -1192060, -15793393,
1869              7251489, -11182180, 24099109, -14456170},
1870         },
1871         {
1872             {5019558, -7907470, 4244127, -14714356, -26933272, 6453165,
1873              -19118182, -13289025, -6231896, -10280736},
1874             {10853594, 10721687, 26480089, 5861829, -22995819, 1972175,
1875              -1866647, -10557898, -3363451, -6441124},
1876             {-17002408, 5906790, 221599, -6563147, 7828208, -13248918, 24362661,
1877              -2008168, -13866408, 7421392},
1878         },
1879         {
1880             {8139927, -6546497, 32257646, -5890546, 30375719, 1886181,
1881              -21175108, 15441252, 28826358, -4123029},
1882             {6267086, 9695052, 7709135, -16603597, -32869068, -1886135,
1883              14795160, -7840124, 13746021, -1742048},
1884             {28584902, 7787108, -6732942, -15050729, 22846041, -7571236,
1885              -3181936, -363524, 4771362, -8419958},
1886         },
1887     },
1888     {
1889         {
1890             {24949256, 6376279, -27466481, -8174608, -18646154, -9930606,
1891              33543569, -12141695, 3569627, 11342593},
1892             {26514989, 4740088, 27912651, 3697550, 19331575, -11472339, 6809886,
1893              4608608, 7325975, -14801071},
1894             {-11618399, -14554430, -24321212, 7655128, -1369274, 5214312,
1895              -27400540, 10258390, -17646694, -8186692},
1896         },
1897         {
1898             {11431204, 15823007, 26570245, 14329124, 18029990, 4796082,
1899              -31446179, 15580664, 9280358, -3973687},
1900             {-160783, -10326257, -22855316, -4304997, -20861367, -13621002,
1901              -32810901, -11181622, -15545091, 4387441},
1902             {-20799378, 12194512, 3937617, -5805892, -27154820, 9340370,
1903              -24513992, 8548137, 20617071, -7482001},
1904         },
1905         {
1906             {-938825, -3930586, -8714311, 16124718, 24603125, -6225393,
1907              -13775352, -11875822, 24345683, 10325460},
1908             {-19855277, -1568885, -22202708, 8714034, 14007766, 6928528,
1909              16318175, -1010689, 4766743, 3552007},
1910             {-21751364, -16730916, 1351763, -803421, -4009670, 3950935, 3217514,
1911              14481909, 10988822, -3994762},
1912         },
1913         {
1914             {15564307, -14311570, 3101243, 5684148, 30446780, -8051356,
1915              12677127, -6505343, -8295852, 13296005},
1916             {-9442290, 6624296, -30298964, -11913677, -4670981, -2057379,
1917              31521204, 9614054, -30000824, 12074674},
1918             {4771191, -135239, 14290749, -13089852, 27992298, 14998318,
1919              -1413936, -1556716, 29832613, -16391035},
1920         },
1921         {
1922             {7064884, -7541174, -19161962, -5067537, -18891269, -2912736,
1923              25825242, 5293297, -27122660, 13101590},
1924             {-2298563, 2439670, -7466610, 1719965, -27267541, -16328445,
1925              32512469, -5317593, -30356070, -4190957},
1926             {-30006540, 10162316, -33180176, 3981723, -16482138, -13070044,
1927              14413974, 9515896, 19568978, 9628812},
1928         },
1929         {
1930             {33053803, 199357, 15894591, 1583059, 27380243, -4580435, -17838894,
1931              -6106839, -6291786, 3437740},
1932             {-18978877, 3884493, 19469877, 12726490, 15913552, 13614290,
1933              -22961733, 70104, 7463304, 4176122},
1934             {-27124001, 10659917, 11482427, -16070381, 12771467, -6635117,
1935              -32719404, -5322751, 24216882, 5944158},
1936         },
1937         {
1938             {8894125, 7450974, -2664149, -9765752, -28080517, -12389115,
1939              19345746, 14680796, 11632993, 5847885},
1940             {26942781, -2315317, 9129564, -4906607, 26024105, 11769399,
1941              -11518837, 6367194, -9727230, 4782140},
1942             {19916461, -4828410, -22910704, -11414391, 25606324, -5972441,
1943              33253853, 8220911, 6358847, -1873857},
1944         },
1945         {
1946             {801428, -2081702, 16569428, 11065167, 29875704, 96627, 7908388,
1947              -4480480, -13538503, 1387155},
1948             {19646058, 5720633, -11416706, 12814209, 11607948, 12749789,
1949              14147075, 15156355, -21866831, 11835260},
1950             {19299512, 1155910, 28703737, 14890794, 2925026, 7269399, 26121523,
1951              15467869, -26560550, 5052483},
1952         },
1953     },
1954     {
1955         {
1956             {-3017432, 10058206, 1980837, 3964243, 22160966, 12322533, -6431123,
1957              -12618185, 12228557, -7003677},
1958             {32944382, 14922211, -22844894, 5188528, 21913450, -8719943,
1959              4001465, 13238564, -6114803, 8653815},
1960             {22865569, -4652735, 27603668, -12545395, 14348958, 8234005,
1961              24808405, 5719875, 28483275, 2841751},
1962         },
1963         {
1964             {-16420968, -1113305, -327719, -12107856, 21886282, -15552774,
1965              -1887966, -315658, 19932058, -12739203},
1966             {-11656086, 10087521, -8864888, -5536143, -19278573, -3055912,
1967              3999228, 13239134, -4777469, -13910208},
1968             {1382174, -11694719, 17266790, 9194690, -13324356, 9720081,
1969              20403944, 11284705, -14013818, 3093230},
1970         },
1971         {
1972             {16650921, -11037932, -1064178, 1570629, -8329746, 7352753, -302424,
1973              16271225, -24049421, -6691850},
1974             {-21911077, -5927941, -4611316, -5560156, -31744103, -10785293,
1975              24123614, 15193618, -21652117, -16739389},
1976             {-9935934, -4289447, -25279823, 4372842, 2087473, 10399484,
1977              31870908, 14690798, 17361620, 11864968},
1978         },
1979         {
1980             {-11307610, 6210372, 13206574, 5806320, -29017692, -13967200,
1981              -12331205, -7486601, -25578460, -16240689},
1982             {14668462, -12270235, 26039039, 15305210, 25515617, 4542480,
1983              10453892, 6577524, 9145645, -6443880},
1984             {5974874, 3053895, -9433049, -10385191, -31865124, 3225009,
1985              -7972642, 3936128, -5652273, -3050304},
1986         },
1987         {
1988             {30625386, -4729400, -25555961, -12792866, -20484575, 7695099,
1989              17097188, -16303496, -27999779, 1803632},
1990             {-3553091, 9865099, -5228566, 4272701, -5673832, -16689700,
1991              14911344, 12196514, -21405489, 7047412},
1992             {20093277, 9920966, -11138194, -5343857, 13161587, 12044805,
1993              -32856851, 4124601, -32343828, -10257566},
1994         },
1995         {
1996             {-20788824, 14084654, -13531713, 7842147, 19119038, -13822605,
1997              4752377, -8714640, -21679658, 2288038},
1998             {-26819236, -3283715, 29965059, 3039786, -14473765, 2540457,
1999              29457502, 14625692, -24819617, 12570232},
2000             {-1063558, -11551823, 16920318, 12494842, 1278292, -5869109,
2001              -21159943, -3498680, -11974704, 4724943},
2002         },
2003         {
2004             {17960970, -11775534, -4140968, -9702530, -8876562, -1410617,
2005              -12907383, -8659932, -29576300, 1903856},
2006             {23134274, -14279132, -10681997, -1611936, 20684485, 15770816,
2007              -12989750, 3190296, 26955097, 14109738},
2008             {15308788, 5320727, -30113809, -14318877, 22902008, 7767164,
2009              29425325, -11277562, 31960942, 11934971},
2010         },
2011         {
2012             {-27395711, 8435796, 4109644, 12222639, -24627868, 14818669,
2013              20638173, 4875028, 10491392, 1379718},
2014             {-13159415, 9197841, 3875503, -8936108, -1383712, -5879801,
2015              33518459, 16176658, 21432314, 12180697},
2016             {-11787308, 11500838, 13787581, -13832590, -22430679, 10140205,
2017              1465425, 12689540, -10301319, -13872883},
2018         },
2019     },
2020     {
2021         {
2022             {5414091, -15386041, -21007664, 9643570, 12834970, 1186149,
2023              -2622916, -1342231, 26128231, 6032912},
2024             {-26337395, -13766162, 32496025, -13653919, 17847801, -12669156,
2025              3604025, 8316894, -25875034, -10437358},
2026             {3296484, 6223048, 24680646, -12246460, -23052020, 5903205,
2027              -8862297, -4639164, 12376617, 3188849},
2028         },
2029         {
2030             {29190488, -14659046, 27549113, -1183516, 3520066, -10697301,
2031              32049515, -7309113, -16109234, -9852307},
2032             {-14744486, -9309156, 735818, -598978, -20407687, -5057904,
2033              25246078, -15795669, 18640741, -960977},
2034             {-6928835, -16430795, 10361374, 5642961, 4910474, 12345252,
2035              -31638386, -494430, 10530747, 1053335},
2036         },
2037         {
2038             {-29265967, -14186805, -13538216, -12117373, -19457059, -10655384,
2039              -31462369, -2948985, 24018831, 15026644},
2040             {-22592535, -3145277, -2289276, 5953843, -13440189, 9425631,
2041              25310643, 13003497, -2314791, -15145616},
2042             {-27419985, -603321, -8043984, -1669117, -26092265, 13987819,
2043              -27297622, 187899, -23166419, -2531735},
2044         },
2045         {
2046             {-21744398, -13810475, 1844840, 5021428, -10434399, -15911473,
2047              9716667, 16266922, -5070217, 726099},
2048             {29370922, -6053998, 7334071, -15342259, 9385287, 2247707,
2049              -13661962, -4839461, 30007388, -15823341},
2050             {-936379, 16086691, 23751945, -543318, -1167538, -5189036, 9137109,
2051              730663, 9835848, 4555336},
2052         },
2053         {
2054             {-23376435, 1410446, -22253753, -12899614, 30867635, 15826977,
2055              17693930, 544696, -11985298, 12422646},
2056             {31117226, -12215734, -13502838, 6561947, -9876867, -12757670,
2057              -5118685, -4096706, 29120153, 13924425},
2058             {-17400879, -14233209, 19675799, -2734756, -11006962, -5858820,
2059              -9383939, -11317700, 7240931, -237388},
2060         },
2061         {
2062             {-31361739, -11346780, -15007447, -5856218, -22453340, -12152771,
2063              1222336, 4389483, 3293637, -15551743},
2064             {-16684801, -14444245, 11038544, 11054958, -13801175, -3338533,
2065              -24319580, 7733547, 12796905, -6335822},
2066             {-8759414, -10817836, -25418864, 10783769, -30615557, -9746811,
2067              -28253339, 3647836, 3222231, -11160462},
2068         },
2069         {
2070             {18606113, 1693100, -25448386, -15170272, 4112353, 10045021,
2071              23603893, -2048234, -7550776, 2484985},
2072             {9255317, -3131197, -12156162, -1004256, 13098013, -9214866,
2073              16377220, -2102812, -19802075, -3034702},
2074             {-22729289, 7496160, -5742199, 11329249, 19991973, -3347502,
2075              -31718148, 9936966, -30097688, -10618797},
2076         },
2077         {
2078             {21878590, -5001297, 4338336, 13643897, -3036865, 13160960,
2079              19708896, 5415497, -7360503, -4109293},
2080             {27736861, 10103576, 12500508, 8502413, -3413016, -9633558,
2081              10436918, -1550276, -23659143, -8132100},
2082             {19492550, -12104365, -29681976, -852630, -3208171, 12403437,
2083              30066266, 8367329, 13243957, 8709688},
2084         },
2085     },
2086     {
2087         {
2088             {12015105, 2801261, 28198131, 10151021, 24818120, -4743133,
2089              -11194191, -5645734, 5150968, 7274186},
2090             {2831366, -12492146, 1478975, 6122054, 23825128, -12733586,
2091              31097299, 6083058, 31021603, -9793610},
2092             {-2529932, -2229646, 445613, 10720828, -13849527, -11505937,
2093              -23507731, 16354465, 15067285, -14147707},
2094         },
2095         {
2096             {7840942, 14037873, -33364863, 15934016, -728213, -3642706,
2097              21403988, 1057586, -19379462, -12403220},
2098             {915865, -16469274, 15608285, -8789130, -24357026, 6060030,
2099              -17371319, 8410997, -7220461, 16527025},
2100             {32922597, -556987, 20336074, -16184568, 10903705, -5384487,
2101              16957574, 52992, 23834301, 6588044},
2102         },
2103         {
2104             {32752030, 11232950, 3381995, -8714866, 22652988, -10744103,
2105              17159699, 16689107, -20314580, -1305992},
2106             {-4689649, 9166776, -25710296, -10847306, 11576752, 12733943,
2107              7924251, -2752281, 1976123, -7249027},
2108             {21251222, 16309901, -2983015, -6783122, 30810597, 12967303, 156041,
2109              -3371252, 12331345, -8237197},
2110         },
2111         {
2112             {8651614, -4477032, -16085636, -4996994, 13002507, 2950805,
2113              29054427, -5106970, 10008136, -4667901},
2114             {31486080, 15114593, -14261250, 12951354, 14369431, -7387845,
2115              16347321, -13662089, 8684155, -10532952},
2116             {19443825, 11385320, 24468943, -9659068, -23919258, 2187569,
2117              -26263207, -6086921, 31316348, 14219878},
2118         },
2119         {
2120             {-28594490, 1193785, 32245219, 11392485, 31092169, 15722801,
2121              27146014, 6992409, 29126555, 9207390},
2122             {32382935, 1110093, 18477781, 11028262, -27411763, -7548111,
2123              -4980517, 10843782, -7957600, -14435730},
2124             {2814918, 7836403, 27519878, -7868156, -20894015, -11553689,
2125              -21494559, 8550130, 28346258, 1994730},
2126         },
2127         {
2128             {-19578299, 8085545, -14000519, -3948622, 2785838, -16231307,
2129              -19516951, 7174894, 22628102, 8115180},
2130             {-30405132, 955511, -11133838, -15078069, -32447087, -13278079,
2131              -25651578, 3317160, -9943017, 930272},
2132             {-15303681, -6833769, 28856490, 1357446, 23421993, 1057177,
2133              24091212, -1388970, -22765376, -10650715},
2134         },
2135         {
2136             {-22751231, -5303997, -12907607, -12768866, -15811511, -7797053,
2137              -14839018, -16554220, -1867018, 8398970},
2138             {-31969310, 2106403, -4736360, 1362501, 12813763, 16200670,
2139              22981545, -6291273, 18009408, -15772772},
2140             {-17220923, -9545221, -27784654, 14166835, 29815394, 7444469,
2141              29551787, -3727419, 19288549, 1325865},
2142         },
2143         {
2144             {15100157, -15835752, -23923978, -1005098, -26450192, 15509408,
2145              12376730, -3479146, 33166107, -8042750},
2146             {20909231, 13023121, -9209752, 16251778, -5778415, -8094914,
2147              12412151, 10018715, 2213263, -13878373},
2148             {32529814, -11074689, 30361439, -16689753, -9135940, 1513226,
2149              22922121, 6382134, -5766928, 8371348},
2150         },
2151     },
2152     {
2153         {
2154             {9923462, 11271500, 12616794, 3544722, -29998368, -1721626,
2155              12891687, -8193132, -26442943, 10486144},
2156             {-22597207, -7012665, 8587003, -8257861, 4084309, -12970062, 361726,
2157              2610596, -23921530, -11455195},
2158             {5408411, -1136691, -4969122, 10561668, 24145918, 14240566,
2159              31319731, -4235541, 19985175, -3436086},
2160         },
2161         {
2162             {-13994457, 16616821, 14549246, 3341099, 32155958, 13648976,
2163              -17577068, 8849297, 65030, 8370684},
2164             {-8320926, -12049626, 31204563, 5839400, -20627288, -1057277,
2165              -19442942, 6922164, 12743482, -9800518},
2166             {-2361371, 12678785, 28815050, 4759974, -23893047, 4884717,
2167              23783145, 11038569, 18800704, 255233},
2168         },
2169         {
2170             {-5269658, -1773886, 13957886, 7990715, 23132995, 728773, 13393847,
2171              9066957, 19258688, -14753793},
2172             {-2936654, -10827535, -10432089, 14516793, -3640786, 4372541,
2173              -31934921, 2209390, -1524053, 2055794},
2174             {580882, 16705327, 5468415, -2683018, -30926419, -14696000,
2175              -7203346, -8994389, -30021019, 7394435},
2176         },
2177         {
2178             {23838809, 1822728, -15738443, 15242727, 8318092, -3733104,
2179              -21672180, -3492205, -4821741, 14799921},
2180             {13345610, 9759151, 3371034, -16137791, 16353039, 8577942, 31129804,
2181              13496856, -9056018, 7402518},
2182             {2286874, -4435931, -20042458, -2008336, -13696227, 5038122,
2183              11006906, -15760352, 8205061, 1607563},
2184         },
2185         {
2186             {14414086, -8002132, 3331830, -3208217, 22249151, -5594188,
2187              18364661, -2906958, 30019587, -9029278},
2188             {-27688051, 1585953, -10775053, 931069, -29120221, -11002319,
2189              -14410829, 12029093, 9944378, 8024},
2190             {4368715, -3709630, 29874200, -15022983, -20230386, -11410704,
2191              -16114594, -999085, -8142388, 5640030},
2192         },
2193         {
2194             {10299610, 13746483, 11661824, 16234854, 7630238, 5998374, 9809887,
2195              -16694564, 15219798, -14327783},
2196             {27425505, -5719081, 3055006, 10660664, 23458024, 595578, -15398605,
2197              -1173195, -18342183, 9742717},
2198             {6744077, 2427284, 26042789, 2720740, -847906, 1118974, 32324614,
2199              7406442, 12420155, 1994844},
2200         },
2201         {
2202             {14012521, -5024720, -18384453, -9578469, -26485342, -3936439,
2203              -13033478, -10909803, 24319929, -6446333},
2204             {16412690, -4507367, 10772641, 15929391, -17068788, -4658621,
2205              10555945, -10484049, -30102368, -4739048},
2206             {22397382, -7767684, -9293161, -12792868, 17166287, -9755136,
2207              -27333065, 6199366, 21880021, -12250760},
2208         },
2209         {
2210             {-4283307, 5368523, -31117018, 8163389, -30323063, 3209128,
2211              16557151, 8890729, 8840445, 4957760},
2212             {-15447727, 709327, -6919446, -10870178, -29777922, 6522332,
2213              -21720181, 12130072, -14796503, 5005757},
2214             {-2114751, -14308128, 23019042, 15765735, -25269683, 6002752,
2215              10183197, -13239326, -16395286, -2176112},
2216         },
2217     },
2218     {
2219         {
2220             {-19025756, 1632005, 13466291, -7995100, -23640451, 16573537,
2221              -32013908, -3057104, 22208662, 2000468},
2222             {3065073, -1412761, -25598674, -361432, -17683065, -5703415,
2223              -8164212, 11248527, -3691214, -7414184},
2224             {10379208, -6045554, 8877319, 1473647, -29291284, -12507580,
2225              16690915, 2553332, -3132688, 16400289},
2226         },
2227         {
2228             {15716668, 1254266, -18472690, 7446274, -8448918, 6344164,
2229              -22097271, -7285580, 26894937, 9132066},
2230             {24158887, 12938817, 11085297, -8177598, -28063478, -4457083,
2231              -30576463, 64452, -6817084, -2692882},
2232             {13488534, 7794716, 22236231, 5989356, 25426474, -12578208, 2350710,
2233              -3418511, -4688006, 2364226},
2234         },
2235         {
2236             {16335052, 9132434, 25640582, 6678888, 1725628, 8517937, -11807024,
2237              -11697457, 15445875, -7798101},
2238             {29004207, -7867081, 28661402, -640412, -12794003, -7943086,
2239              31863255, -4135540, -278050, -15759279},
2240             {-6122061, -14866665, -28614905, 14569919, -10857999, -3591829,
2241              10343412, -6976290, -29828287, -10815811},
2242         },
2243         {
2244             {27081650, 3463984, 14099042, -4517604, 1616303, -6205604, 29542636,
2245              15372179, 17293797, 960709},
2246             {20263915, 11434237, -5765435, 11236810, 13505955, -10857102,
2247              -16111345, 6493122, -19384511, 7639714},
2248             {-2830798, -14839232, 25403038, -8215196, -8317012, -16173699,
2249              18006287, -16043750, 29994677, -15808121},
2250         },
2251         {
2252             {9769828, 5202651, -24157398, -13631392, -28051003, -11561624,
2253              -24613141, -13860782, -31184575, 709464},
2254             {12286395, 13076066, -21775189, -1176622, -25003198, 4057652,
2255              -32018128, -8890874, 16102007, 13205847},
2256             {13733362, 5599946, 10557076, 3195751, -5557991, 8536970, -25540170,
2257              8525972, 10151379, 10394400},
2258         },
2259         {
2260             {4024660, -16137551, 22436262, 12276534, -9099015, -2686099,
2261              19698229, 11743039, -33302334, 8934414},
2262             {-15879800, -4525240, -8580747, -2934061, 14634845, -698278,
2263              -9449077, 3137094, -11536886, 11721158},
2264             {17555939, -5013938, 8268606, 2331751, -22738815, 9761013, 9319229,
2265              8835153, -9205489, -1280045},
2266         },
2267         {
2268             {-461409, -7830014, 20614118, 16688288, -7514766, -4807119,
2269              22300304, 505429, 6108462, -6183415},
2270             {-5070281, 12367917, -30663534, 3234473, 32617080, -8422642,
2271              29880583, -13483331, -26898490, -7867459},
2272             {-31975283, 5726539, 26934134, 10237677, -3173717, -605053,
2273              24199304, 3795095, 7592688, -14992079},
2274         },
2275         {
2276             {21594432, -14964228, 17466408, -4077222, 32537084, 2739898,
2277              6407723, 12018833, -28256052, 4298412},
2278             {-20650503, -11961496, -27236275, 570498, 3767144, -1717540,
2279              13891942, -1569194, 13717174, 10805743},
2280             {-14676630, -15644296, 15287174, 11927123, 24177847, -8175568,
2281              -796431, 14860609, -26938930, -5863836},
2282         },
2283     },
2284     {
2285         {
2286             {12962541, 5311799, -10060768, 11658280, 18855286, -7954201,
2287              13286263, -12808704, -4381056, 9882022},
2288             {18512079, 11319350, -20123124, 15090309, 18818594, 5271736,
2289              -22727904, 3666879, -23967430, -3299429},
2290             {-6789020, -3146043, 16192429, 13241070, 15898607, -14206114,
2291              -10084880, -6661110, -2403099, 5276065},
2292         },
2293         {
2294             {30169808, -5317648, 26306206, -11750859, 27814964, 7069267,
2295              7152851, 3684982, 1449224, 13082861},
2296             {10342826, 3098505, 2119311, 193222, 25702612, 12233820, 23697382,
2297              15056736, -21016438, -8202000},
2298             {-33150110, 3261608, 22745853, 7948688, 19370557, -15177665,
2299              -26171976, 6482814, -10300080, -11060101},
2300         },
2301         {
2302             {32869458, -5408545, 25609743, 15678670, -10687769, -15471071,
2303              26112421, 2521008, -22664288, 6904815},
2304             {29506923, 4457497, 3377935, -9796444, -30510046, 12935080, 1561737,
2305              3841096, -29003639, -6657642},
2306             {10340844, -6630377, -18656632, -2278430, 12621151, -13339055,
2307              30878497, -11824370, -25584551, 5181966},
2308         },
2309         {
2310             {25940115, -12658025, 17324188, -10307374, -8671468, 15029094,
2311              24396252, -16450922, -2322852, -12388574},
2312             {-21765684, 9916823, -1300409, 4079498, -1028346, 11909559, 1782390,
2313              12641087, 20603771, -6561742},
2314             {-18882287, -11673380, 24849422, 11501709, 13161720, -4768874,
2315              1925523, 11914390, 4662781, 7820689},
2316         },
2317         {
2318             {12241050, -425982, 8132691, 9393934, 32846760, -1599620, 29749456,
2319              12172924, 16136752, 15264020},
2320             {-10349955, -14680563, -8211979, 2330220, -17662549, -14545780,
2321              10658213, 6671822, 19012087, 3772772},
2322             {3753511, -3421066, 10617074, 2028709, 14841030, -6721664, 28718732,
2323              -15762884, 20527771, 12988982},
2324         },
2325         {
2326             {-14822485, -5797269, -3707987, 12689773, -898983, -10914866,
2327              -24183046, -10564943, 3299665, -12424953},
2328             {-16777703, -15253301, -9642417, 4978983, 3308785, 8755439, 6943197,
2329              6461331, -25583147, 8991218},
2330             {-17226263, 1816362, -1673288, -6086439, 31783888, -8175991,
2331              -32948145, 7417950, -30242287, 1507265},
2332         },
2333         {
2334             {29692663, 6829891, -10498800, 4334896, 20945975, -11906496,
2335              -28887608, 8209391, 14606362, -10647073},
2336             {-3481570, 8707081, 32188102, 5672294, 22096700, 1711240, -33020695,
2337              9761487, 4170404, -2085325},
2338             {-11587470, 14855945, -4127778, -1531857, -26649089, 15084046,
2339              22186522, 16002000, -14276837, -8400798},
2340         },
2341         {
2342             {-4811456, 13761029, -31703877, -2483919, -3312471, 7869047,
2343              -7113572, -9620092, 13240845, 10965870},
2344             {-7742563, -8256762, -14768334, -13656260, -23232383, 12387166,
2345              4498947, 14147411, 29514390, 4302863},
2346             {-13413405, -12407859, 20757302, -13801832, 14785143, 8976368,
2347              -5061276, -2144373, 17846988, -13971927},
2348         },
2349     },
2350     {
2351         {
2352             {-2244452, -754728, -4597030, -1066309, -6247172, 1455299,
2353              -21647728, -9214789, -5222701, 12650267},
2354             {-9906797, -16070310, 21134160, 12198166, -27064575, 708126, 387813,
2355              13770293, -19134326, 10958663},
2356             {22470984, 12369526, 23446014, -5441109, -21520802, -9698723,
2357              -11772496, -11574455, -25083830, 4271862},
2358         },
2359         {
2360             {-25169565, -10053642, -19909332, 15361595, -5984358, 2159192,
2361              75375, -4278529, -32526221, 8469673},
2362             {15854970, 4148314, -8893890, 7259002, 11666551, 13824734,
2363              -30531198, 2697372, 24154791, -9460943},
2364             {15446137, -15806644, 29759747, 14019369, 30811221, -9610191,
2365              -31582008, 12840104, 24913809, 9815020},
2366         },
2367         {
2368             {-4709286, -5614269, -31841498, -12288893, -14443537, 10799414,
2369              -9103676, 13438769, 18735128, 9466238},
2370             {11933045, 9281483, 5081055, -5183824, -2628162, -4905629, -7727821,
2371              -10896103, -22728655, 16199064},
2372             {14576810, 379472, -26786533, -8317236, -29426508, -10812974,
2373              -102766, 1876699, 30801119, 2164795},
2374         },
2375         {
2376             {15995086, 3199873, 13672555, 13712240, -19378835, -4647646,
2377              -13081610, -15496269, -13492807, 1268052},
2378             {-10290614, -3659039, -3286592, 10948818, 23037027, 3794475,
2379              -3470338, -12600221, -17055369, 3565904},
2380             {29210088, -9419337, -5919792, -4952785, 10834811, -13327726,
2381              -16512102, -10820713, -27162222, -14030531},
2382         },
2383         {
2384             {-13161890, 15508588, 16663704, -8156150, -28349942, 9019123,
2385              -29183421, -3769423, 2244111, -14001979},
2386             {-5152875, -3800936, -9306475, -6071583, 16243069, 14684434,
2387              -25673088, -16180800, 13491506, 4641841},
2388             {10813417, 643330, -19188515, -728916, 30292062, -16600078,
2389              27548447, -7721242, 14476989, -12767431},
2390         },
2391         {
2392             {10292079, 9984945, 6481436, 8279905, -7251514, 7032743, 27282937,
2393              -1644259, -27912810, 12651324},
2394             {-31185513, -813383, 22271204, 11835308, 10201545, 15351028,
2395              17099662, 3988035, 21721536, -3148940},
2396             {10202177, -6545839, -31373232, -9574638, -32150642, -8119683,
2397              -12906320, 3852694, 13216206, 14842320},
2398         },
2399         {
2400             {-15815640, -10601066, -6538952, -7258995, -6984659, -6581778,
2401              -31500847, 13765824, -27434397, 9900184},
2402             {14465505, -13833331, -32133984, -14738873, -27443187, 12990492,
2403              33046193, 15796406, -7051866, -8040114},
2404             {30924417, -8279620, 6359016, -12816335, 16508377, 9071735,
2405              -25488601, 15413635, 9524356, -7018878},
2406         },
2407         {
2408             {12274201, -13175547, 32627641, -1785326, 6736625, 13267305,
2409              5237659, -5109483, 15663516, 4035784},
2410             {-2951309, 8903985, 17349946, 601635, -16432815, -4612556,
2411              -13732739, -15889334, -22258478, 4659091},
2412             {-16916263, -4952973, -30393711, -15158821, 20774812, 15897498,
2413              5736189, 15026997, -2178256, -13455585},
2414         },
2415     },
2416     {
2417         {
2418             {-8858980, -2219056, 28571666, -10155518, -474467, -10105698,
2419              -3801496, 278095, 23440562, -290208},
2420             {10226241, -5928702, 15139956, 120818, -14867693, 5218603, 32937275,
2421              11551483, -16571960, -7442864},
2422             {17932739, -12437276, -24039557, 10749060, 11316803, 7535897,
2423              22503767, 5561594, -3646624, 3898661},
2424         },
2425         {
2426             {7749907, -969567, -16339731, -16464, -25018111, 15122143, -1573531,
2427              7152530, 21831162, 1245233},
2428             {26958459, -14658026, 4314586, 8346991, -5677764, 11960072,
2429              -32589295, -620035, -30402091, -16716212},
2430             {-12165896, 9166947, 33491384, 13673479, 29787085, 13096535,
2431              6280834, 14587357, -22338025, 13987525},
2432         },
2433         {
2434             {-24349909, 7778775, 21116000, 15572597, -4833266, -5357778,
2435              -4300898, -5124639, -7469781, -2858068},
2436             {9681908, -6737123, -31951644, 13591838, -6883821, 386950, 31622781,
2437              6439245, -14581012, 4091397},
2438             {-8426427, 1470727, -28109679, -1596990, 3978627, -5123623,
2439              -19622683, 12092163, 29077877, -14741988},
2440         },
2441         {
2442             {5269168, -6859726, -13230211, -8020715, 25932563, 1763552,
2443              -5606110, -5505881, -20017847, 2357889},
2444             {32264008, -15407652, -5387735, -1160093, -2091322, -3946900,
2445              23104804, -12869908, 5727338, 189038},
2446             {14609123, -8954470, -6000566, -16622781, -14577387, -7743898,
2447              -26745169, 10942115, -25888931, -14884697},
2448         },
2449         {
2450             {20513500, 5557931, -15604613, 7829531, 26413943, -2019404,
2451              -21378968, 7471781, 13913677, -5137875},
2452             {-25574376, 11967826, 29233242, 12948236, -6754465, 4713227,
2453              -8940970, 14059180, 12878652, 8511905},
2454             {-25656801, 3393631, -2955415, -7075526, -2250709, 9366908,
2455              -30223418, 6812974, 5568676, -3127656},
2456         },
2457         {
2458             {11630004, 12144454, 2116339, 13606037, 27378885, 15676917,
2459              -17408753, -13504373, -14395196, 8070818},
2460             {27117696, -10007378, -31282771, -5570088, 1127282, 12772488,
2461              -29845906, 10483306, -11552749, -1028714},
2462             {10637467, -5688064, 5674781, 1072708, -26343588, -6982302,
2463              -1683975, 9177853, -27493162, 15431203},
2464         },
2465         {
2466             {20525145, 10892566, -12742472, 12779443, -29493034, 16150075,
2467              -28240519, 14943142, -15056790, -7935931},
2468             {-30024462, 5626926, -551567, -9981087, 753598, 11981191, 25244767,
2469              -3239766, -3356550, 9594024},
2470             {-23752644, 2636870, -5163910, -10103818, 585134, 7877383, 11345683,
2471              -6492290, 13352335, -10977084},
2472         },
2473         {
2474             {-1931799, -5407458, 3304649, -12884869, 17015806, -4877091,
2475              -29783850, -7752482, -13215537, -319204},
2476             {20239939, 6607058, 6203985, 3483793, -18386976, -779229, -20723742,
2477              15077870, -22750759, 14523817},
2478             {27406042, -6041657, 27423596, -4497394, 4996214, 10002360,
2479              -28842031, -4545494, -30172742, -4805667},
2480         },
2481     },
2482     {
2483         {
2484             {11374242, 12660715, 17861383, -12540833, 10935568, 1099227,
2485              -13886076, -9091740, -27727044, 11358504},
2486             {-12730809, 10311867, 1510375, 10778093, -2119455, -9145702,
2487              32676003, 11149336, -26123651, 4985768},
2488             {-19096303, 341147, -6197485, -239033, 15756973, -8796662, -983043,
2489              13794114, -19414307, -15621255},
2490         },
2491         {
2492             {6490081, 11940286, 25495923, -7726360, 8668373, -8751316, 3367603,
2493              6970005, -1691065, -9004790},
2494             {1656497, 13457317, 15370807, 6364910, 13605745, 8362338, -19174622,
2495              -5475723, -16796596, -5031438},
2496             {-22273315, -13524424, -64685, -4334223, -18605636, -10921968,
2497              -20571065, -7007978, -99853, -10237333},
2498         },
2499         {
2500             {17747465, 10039260, 19368299, -4050591, -20630635, -16041286,
2501              31992683, -15857976, -29260363, -5511971},
2502             {31932027, -4986141, -19612382, 16366580, 22023614, 88450, 11371999,
2503              -3744247, 4882242, -10626905},
2504             {29796507, 37186, 19818052, 10115756, -11829032, 3352736, 18551198,
2505              3272828, -5190932, -4162409},
2506         },
2507         {
2508             {12501286, 4044383, -8612957, -13392385, -32430052, 5136599,
2509              -19230378, -3529697, 330070, -3659409},
2510             {6384877, 2899513, 17807477, 7663917, -2358888, 12363165, 25366522,
2511              -8573892, -271295, 12071499},
2512             {-8365515, -4042521, 25133448, -4517355, -6211027, 2265927,
2513              -32769618, 1936675, -5159697, 3829363},
2514         },
2515         {
2516             {28425966, -5835433, -577090, -4697198, -14217555, 6870930, 7921550,
2517              -6567787, 26333140, 14267664},
2518             {-11067219, 11871231, 27385719, -10559544, -4585914, -11189312,
2519              10004786, -8709488, -21761224, 8930324},
2520             {-21197785, -16396035, 25654216, -1725397, 12282012, 11008919,
2521              1541940, 4757911, -26491501, -16408940},
2522         },
2523         {
2524             {13537262, -7759490, -20604840, 10961927, -5922820, -13218065,
2525              -13156584, 6217254, -15943699, 13814990},
2526             {-17422573, 15157790, 18705543, 29619, 24409717, -260476, 27361681,
2527              9257833, -1956526, -1776914},
2528             {-25045300, -10191966, 15366585, 15166509, -13105086, 8423556,
2529              -29171540, 12361135, -18685978, 4578290},
2530         },
2531         {
2532             {24579768, 3711570, 1342322, -11180126, -27005135, 14124956,
2533              -22544529, 14074919, 21964432, 8235257},
2534             {-6528613, -2411497, 9442966, -5925588, 12025640, -1487420,
2535              -2981514, -1669206, 13006806, 2355433},
2536             {-16304899, -13605259, -6632427, -5142349, 16974359, -10911083,
2537              27202044, 1719366, 1141648, -12796236},
2538         },
2539         {
2540             {-12863944, -13219986, -8318266, -11018091, -6810145, -4843894,
2541              13475066, -3133972, 32674895, 13715045},
2542             {11423335, -5468059, 32344216, 8962751, 24989809, 9241752,
2543              -13265253, 16086212, -28740881, -15642093},
2544             {-1409668, 12530728, -6368726, 10847387, 19531186, -14132160,
2545              -11709148, 7791794, -27245943, 4383347},
2546         },
2547     },
2548     {
2549         {
2550             {-28970898, 5271447, -1266009, -9736989, -12455236, 16732599,
2551              -4862407, -4906449, 27193557, 6245191},
2552             {-15193956, 5362278, -1783893, 2695834, 4960227, 12840725, 23061898,
2553              3260492, 22510453, 8577507},
2554             {-12632451, 11257346, -32692994, 13548177, -721004, 10879011,
2555              31168030, 13952092, -29571492, -3635906},
2556         },
2557         {
2558             {3877321, -9572739, 32416692, 5405324, -11004407, -13656635,
2559              3759769, 11935320, 5611860, 8164018},
2560             {-16275802, 14667797, 15906460, 12155291, -22111149, -9039718,
2561              32003002, -8832289, 5773085, -8422109},
2562             {-23788118, -8254300, 1950875, 8937633, 18686727, 16459170, -905725,
2563              12376320, 31632953, 190926},
2564         },
2565         {
2566             {-24593607, -16138885, -8423991, 13378746, 14162407, 6901328,
2567              -8288749, 4508564, -25341555, -3627528},
2568             {8884438, -5884009, 6023974, 10104341, -6881569, -4941533, 18722941,
2569              -14786005, -1672488, 827625},
2570             {-32720583, -16289296, -32503547, 7101210, 13354605, 2659080,
2571              -1800575, -14108036, -24878478, 1541286},
2572         },
2573         {
2574             {2901347, -1117687, 3880376, -10059388, -17620940, -3612781,
2575              -21802117, -3567481, 20456845, -1885033},
2576             {27019610, 12299467, -13658288, -1603234, -12861660, -4861471,
2577              -19540150, -5016058, 29439641, 15138866},
2578             {21536104, -6626420, -32447818, -10690208, -22408077, 5175814,
2579              -5420040, -16361163, 7779328, 109896},
2580         },
2581         {
2582             {30279744, 14648750, -8044871, 6425558, 13639621, -743509, 28698390,
2583              12180118, 23177719, -554075},
2584             {26572847, 3405927, -31701700, 12890905, -19265668, 5335866,
2585              -6493768, 2378492, 4439158, -13279347},
2586             {-22716706, 3489070, -9225266, -332753, 18875722, -1140095,
2587              14819434, -12731527, -17717757, -5461437},
2588         },
2589         {
2590             {-5056483, 16566551, 15953661, 3767752, -10436499, 15627060,
2591              -820954, 2177225, 8550082, -15114165},
2592             {-18473302, 16596775, -381660, 15663611, 22860960, 15585581,
2593              -27844109, -3582739, -23260460, -8428588},
2594             {-32480551, 15707275, -8205912, -5652081, 29464558, 2713815,
2595              -22725137, 15860482, -21902570, 1494193},
2596         },
2597         {
2598             {-19562091, -14087393, -25583872, -9299552, 13127842, 759709,
2599              21923482, 16529112, 8742704, 12967017},
2600             {-28464899, 1553205, 32536856, -10473729, -24691605, -406174,
2601              -8914625, -2933896, -29903758, 15553883},
2602             {21877909, 3230008, 9881174, 10539357, -4797115, 2841332, 11543572,
2603              14513274, 19375923, -12647961},
2604         },
2605         {
2606             {8832269, -14495485, 13253511, 5137575, 5037871, 4078777, 24880818,
2607              -6222716, 2862653, 9455043},
2608             {29306751, 5123106, 20245049, -14149889, 9592566, 8447059, -2077124,
2609              -2990080, 15511449, 4789663},
2610             {-20679756, 7004547, 8824831, -9434977, -4045704, -3750736,
2611              -5754762, 108893, 23513200, 16652362},
2612         },
2613     },
2614     {
2615         {
2616             {-33256173, 4144782, -4476029, -6579123, 10770039, -7155542,
2617              -6650416, -12936300, -18319198, 10212860},
2618             {2756081, 8598110, 7383731, -6859892, 22312759, -1105012, 21179801,
2619              2600940, -9988298, -12506466},
2620             {-24645692, 13317462, -30449259, -15653928, 21365574, -10869657,
2621              11344424, 864440, -2499677, -16710063},
2622         },
2623         {
2624             {-26432803, 6148329, -17184412, -14474154, 18782929, -275997,
2625              -22561534, 211300, 2719757, 4940997},
2626             {-1323882, 3911313, -6948744, 14759765, -30027150, 7851207,
2627              21690126, 8518463, 26699843, 5276295},
2628             {-13149873, -6429067, 9396249, 365013, 24703301, -10488939, 1321586,
2629              149635, -15452774, 7159369},
2630         },
2631         {
2632             {9987780, -3404759, 17507962, 9505530, 9731535, -2165514, 22356009,
2633              8312176, 22477218, -8403385},
2634             {18155857, -16504990, 19744716, 9006923, 15154154, -10538976,
2635              24256460, -4864995, -22548173, 9334109},
2636             {2986088, -4911893, 10776628, -3473844, 10620590, -7083203,
2637              -21413845, 14253545, -22587149, 536906},
2638         },
2639         {
2640             {4377756, 8115836, 24567078, 15495314, 11625074, 13064599, 7390551,
2641              10589625, 10838060, -15420424},
2642             {-19342404, 867880, 9277171, -3218459, -14431572, -1986443,
2643              19295826, -15796950, 6378260, 699185},
2644             {7895026, 4057113, -7081772, -13077756, -17886831, -323126, -716039,
2645              15693155, -5045064, -13373962},
2646         },
2647         {
2648             {-7737563, -5869402, -14566319, -7406919, 11385654, 13201616,
2649              31730678, -10962840, -3918636, -9669325},
2650             {10188286, -15770834, -7336361, 13427543, 22223443, 14896287,
2651              30743455, 7116568, -21786507, 5427593},
2652             {696102, 13206899, 27047647, -10632082, 15285305, -9853179,
2653              10798490, -4578720, 19236243, 12477404},
2654         },
2655         {
2656             {-11229439, 11243796, -17054270, -8040865, -788228, -8167967,
2657              -3897669, 11180504, -23169516, 7733644},
2658             {17800790, -14036179, -27000429, -11766671, 23887827, 3149671,
2659              23466177, -10538171, 10322027, 15313801},
2660             {26246234, 11968874, 32263343, -5468728, 6830755, -13323031,
2661              -15794704, -101982, -24449242, 10890804},
2662         },
2663         {
2664             {-31365647, 10271363, -12660625, -6267268, 16690207, -13062544,
2665              -14982212, 16484931, 25180797, -5334884},
2666             {-586574, 10376444, -32586414, -11286356, 19801893, 10997610,
2667              2276632, 9482883, 316878, 13820577},
2668             {-9882808, -4510367, -2115506, 16457136, -11100081, 11674996,
2669              30756178, -7515054, 30696930, -3712849},
2670         },
2671         {
2672             {32988917, -9603412, 12499366, 7910787, -10617257, -11931514,
2673              -7342816, -9985397, -32349517, 7392473},
2674             {-8855661, 15927861, 9866406, -3649411, -2396914, -16655781,
2675              -30409476, -9134995, 25112947, -2926644},
2676             {-2504044, -436966, 25621774, -5678772, 15085042, -5479877,
2677              -24884878, -13526194, 5537438, -13914319},
2678         },
2679     },
2680     {
2681         {
2682             {-11225584, 2320285, -9584280, 10149187, -33444663, 5808648,
2683              -14876251, -1729667, 31234590, 6090599},
2684             {-9633316, 116426, 26083934, 2897444, -6364437, -2688086, 609721,
2685              15878753, -6970405, -9034768},
2686             {-27757857, 247744, -15194774, -9002551, 23288161, -10011936,
2687              -23869595, 6503646, 20650474, 1804084},
2688         },
2689         {
2690             {-27589786, 15456424, 8972517, 8469608, 15640622, 4439847, 3121995,
2691              -10329713, 27842616, -202328},
2692             {-15306973, 2839644, 22530074, 10026331, 4602058, 5048462, 28248656,
2693              5031932, -11375082, 12714369},
2694             {20807691, -7270825, 29286141, 11421711, -27876523, -13868230,
2695              -21227475, 1035546, -19733229, 12796920},
2696         },
2697         {
2698             {12076899, -14301286, -8785001, -11848922, -25012791, 16400684,
2699              -17591495, -12899438, 3480665, -15182815},
2700             {-32361549, 5457597, 28548107, 7833186, 7303070, -11953545,
2701              -24363064, -15921875, -33374054, 2771025},
2702             {-21389266, 421932, 26597266, 6860826, 22486084, -6737172,
2703              -17137485, -4210226, -24552282, 15673397},
2704         },
2705         {
2706             {-20184622, 2338216, 19788685, -9620956, -4001265, -8740893,
2707              -20271184, 4733254, 3727144, -12934448},
2708             {6120119, 814863, -11794402, -622716, 6812205, -15747771, 2019594,
2709              7975683, 31123697, -10958981},
2710             {30069250, -11435332, 30434654, 2958439, 18399564, -976289,
2711              12296869, 9204260, -16432438, 9648165},
2712         },
2713         {
2714             {32705432, -1550977, 30705658, 7451065, -11805606, 9631813, 3305266,
2715              5248604, -26008332, -11377501},
2716             {17219865, 2375039, -31570947, -5575615, -19459679, 9219903, 294711,
2717              15298639, 2662509, -16297073},
2718             {-1172927, -7558695, -4366770, -4287744, -21346413, -8434326,
2719              32087529, -1222777, 32247248, -14389861},
2720         },
2721         {
2722             {14312628, 1221556, 17395390, -8700143, -4945741, -8684635,
2723              -28197744, -9637817, -16027623, -13378845},
2724             {-1428825, -9678990, -9235681, 6549687, -7383069, -468664, 23046502,
2725              9803137, 17597934, 2346211},
2726             {18510800, 15337574, 26171504, 981392, -22241552, 7827556,
2727              -23491134, -11323352, 3059833, -11782870},
2728         },
2729         {
2730             {10141598, 6082907, 17829293, -1947643, 9830092, 13613136,
2731              -25556636, -5544586, -33502212, 3592096},
2732             {33114168, -15889352, -26525686, -13343397, 33076705, 8716171,
2733              1151462, 1521897, -982665, -6837803},
2734             {-32939165, -4255815, 23947181, -324178, -33072974, -12305637,
2735              -16637686, 3891704, 26353178, 693168},
2736         },
2737         {
2738             {30374239, 1595580, -16884039, 13186931, 4600344, 406904, 9585294,
2739              -400668, 31375464, 14369965},
2740             {-14370654, -7772529, 1510301, 6434173, -18784789, -6262728,
2741              32732230, -13108839, 17901441, 16011505},
2742             {18171223, -11934626, -12500402, 15197122, -11038147, -15230035,
2743              -19172240, -16046376, 8764035, 12309598},
2744         },
2745     },
2746     {
2747         {
2748             {5975908, -5243188, -19459362, -9681747, -11541277, 14015782,
2749              -23665757, 1228319, 17544096, -10593782},
2750             {5811932, -1715293, 3442887, -2269310, -18367348, -8359541,
2751              -18044043, -15410127, -5565381, 12348900},
2752             {-31399660, 11407555, 25755363, 6891399, -3256938, 14872274,
2753              -24849353, 8141295, -10632534, -585479},
2754         },
2755         {
2756             {-12675304, 694026, -5076145, 13300344, 14015258, -14451394,
2757              -9698672, -11329050, 30944593, 1130208},
2758             {8247766, -6710942, -26562381, -7709309, -14401939, -14648910,
2759              4652152, 2488540, 23550156, -271232},
2760             {17294316, -3788438, 7026748, 15626851, 22990044, 113481, 2267737,
2761              -5908146, -408818, -137719},
2762         },
2763         {
2764             {16091085, -16253926, 18599252, 7340678, 2137637, -1221657,
2765              -3364161, 14550936, 3260525, -7166271},
2766             {-4910104, -13332887, 18550887, 10864893, -16459325, -7291596,
2767              -23028869, -13204905, -12748722, 2701326},
2768             {-8574695, 16099415, 4629974, -16340524, -20786213, -6005432,
2769              -10018363, 9276971, 11329923, 1862132},
2770         },
2771         {
2772             {14763076, -15903608, -30918270, 3689867, 3511892, 10313526,
2773              -21951088, 12219231, -9037963, -940300},
2774             {8894987, -3446094, 6150753, 3013931, 301220, 15693451, -31981216,
2775              -2909717, -15438168, 11595570},
2776             {15214962, 3537601, -26238722, -14058872, 4418657, -15230761,
2777              13947276, 10730794, -13489462, -4363670},
2778         },
2779         {
2780             {-2538306, 7682793, 32759013, 263109, -29984731, -7955452,
2781              -22332124, -10188635, 977108, 699994},
2782             {-12466472, 4195084, -9211532, 550904, -15565337, 12917920,
2783              19118110, -439841, -30534533, -14337913},
2784             {31788461, -14507657, 4799989, 7372237, 8808585, -14747943, 9408237,
2785              -10051775, 12493932, -5409317},
2786         },
2787         {
2788             {-25680606, 5260744, -19235809, -6284470, -3695942, 16566087,
2789              27218280, 2607121, 29375955, 6024730},
2790             {842132, -2794693, -4763381, -8722815, 26332018, -12405641,
2791              11831880, 6985184, -9940361, 2854096},
2792             {-4847262, -7969331, 2516242, -5847713, 9695691, -7221186, 16512645,
2793              960770, 12121869, 16648078},
2794         },
2795         {
2796             {-15218652, 14667096, -13336229, 2013717, 30598287, -464137,
2797              -31504922, -7882064, 20237806, 2838411},
2798             {-19288047, 4453152, 15298546, -16178388, 22115043, -15972604,
2799              12544294, -13470457, 1068881, -12499905},
2800             {-9558883, -16518835, 33238498, 13506958, 30505848, -1114596,
2801              -8486907, -2630053, 12521378, 4845654},
2802         },
2803         {
2804             {-28198521, 10744108, -2958380, 10199664, 7759311, -13088600,
2805              3409348, -873400, -6482306, -12885870},
2806             {-23561822, 6230156, -20382013, 10655314, -24040585, -11621172,
2807              10477734, -1240216, -3113227, 13974498},
2808             {12966261, 15550616, -32038948, -1615346, 21025980, -629444,
2809              5642325, 7188737, 18895762, 12629579},
2810         },
2811     },
2812     {
2813         {
2814             {14741879, -14946887, 22177208, -11721237, 1279741, 8058600,
2815              11758140, 789443, 32195181, 3895677},
2816             {10758205, 15755439, -4509950, 9243698, -4879422, 6879879, -2204575,
2817              -3566119, -8982069, 4429647},
2818             {-2453894, 15725973, -20436342, -10410672, -5803908, -11040220,
2819              -7135870, -11642895, 18047436, -15281743},
2820         },
2821         {
2822             {-25173001, -11307165, 29759956, 11776784, -22262383, -15820455,
2823              10993114, -12850837, -17620701, -9408468},
2824             {21987233, 700364, -24505048, 14972008, -7774265, -5718395,
2825              32155026, 2581431, -29958985, 8773375},
2826             {-25568350, 454463, -13211935, 16126715, 25240068, 8594567,
2827              20656846, 12017935, -7874389, -13920155},
2828         },
2829         {
2830             {6028182, 6263078, -31011806, -11301710, -818919, 2461772,
2831              -31841174, -5468042, -1721788, -2776725},
2832             {-12278994, 16624277, 987579, -5922598, 32908203, 1248608, 7719845,
2833              -4166698, 28408820, 6816612},
2834             {-10358094, -8237829, 19549651, -12169222, 22082623, 16147817,
2835              20613181, 13982702, -10339570, 5067943},
2836         },
2837         {
2838             {-30505967, -3821767, 12074681, 13582412, -19877972, 2443951,
2839              -19719286, 12746132, 5331210, -10105944},
2840             {30528811, 3601899, -1957090, 4619785, -27361822, -15436388,
2841              24180793, -12570394, 27679908, -1648928},
2842             {9402404, -13957065, 32834043, 10838634, -26580150, -13237195,
2843              26653274, -8685565, 22611444, -12715406},
2844         },
2845         {
2846             {22190590, 1118029, 22736441, 15130463, -30460692, -5991321,
2847              19189625, -4648942, 4854859, 6622139},
2848             {-8310738, -2953450, -8262579, -3388049, -10401731, -271929,
2849              13424426, -3567227, 26404409, 13001963},
2850             {-31241838, -15415700, -2994250, 8939346, 11562230, -12840670,
2851              -26064365, -11621720, -15405155, 11020693},
2852         },
2853         {
2854             {1866042, -7949489, -7898649, -10301010, 12483315, 13477547,
2855              3175636, -12424163, 28761762, 1406734},
2856             {-448555, -1777666, 13018551, 3194501, -9580420, -11161737,
2857              24760585, -4347088, 25577411, -13378680},
2858             {-24290378, 4759345, -690653, -1852816, 2066747, 10693769,
2859              -29595790, 9884936, -9368926, 4745410},
2860         },
2861         {
2862             {-9141284, 6049714, -19531061, -4341411, -31260798, 9944276,
2863              -15462008, -11311852, 10931924, -11931931},
2864             {-16561513, 14112680, -8012645, 4817318, -8040464, -11414606,
2865              -22853429, 10856641, -20470770, 13434654},
2866             {22759489, -10073434, -16766264, -1871422, 13637442, -10168091,
2867              1765144, -12654326, 28445307, -5364710},
2868         },
2869         {
2870             {29875063, 12493613, 2795536, -3786330, 1710620, 15181182,
2871              -10195717, -8788675, 9074234, 1167180},
2872             {-26205683, 11014233, -9842651, -2635485, -26908120, 7532294,
2873              -18716888, -9535498, 3843903, 9367684},
2874             {-10969595, -6403711, 9591134, 9582310, 11349256, 108879, 16235123,
2875              8601684, -139197, 4242895},
2876         },
2877     },
2878     {
2879         {
2880             {22092954, -13191123, -2042793, -11968512, 32186753, -11517388,
2881              -6574341, 2470660, -27417366, 16625501},
2882             {-11057722, 3042016, 13770083, -9257922, 584236, -544855, -7770857,
2883              2602725, -27351616, 14247413},
2884             {6314175, -10264892, -32772502, 15957557, -10157730, 168750,
2885              -8618807, 14290061, 27108877, -1180880},
2886         },
2887         {
2888             {-8586597, -7170966, 13241782, 10960156, -32991015, -13794596,
2889              33547976, -11058889, -27148451, 981874},
2890             {22833440, 9293594, -32649448, -13618667, -9136966, 14756819,
2891              -22928859, -13970780, -10479804, -16197962},
2892             {-7768587, 3326786, -28111797, 10783824, 19178761, 14905060,
2893              22680049, 13906969, -15933690, 3797899},
2894         },
2895         {
2896             {21721356, -4212746, -12206123, 9310182, -3882239, -13653110,
2897              23740224, -2709232, 20491983, -8042152},
2898             {9209270, -15135055, -13256557, -6167798, -731016, 15289673,
2899              25947805, 15286587, 30997318, -6703063},
2900             {7392032, 16618386, 23946583, -8039892, -13265164, -1533858,
2901              -14197445, -2321576, 17649998, -250080},
2902         },
2903         {
2904             {-9301088, -14193827, 30609526, -3049543, -25175069, -1283752,
2905              -15241566, -9525724, -2233253, 7662146},
2906             {-17558673, 1763594, -33114336, 15908610, -30040870, -12174295,
2907              7335080, -8472199, -3174674, 3440183},
2908             {-19889700, -5977008, -24111293, -9688870, 10799743, -16571957,
2909              40450, -4431835, 4862400, 1133},
2910         },
2911         {
2912             {-32856209, -7873957, -5422389, 14860950, -16319031, 7956142,
2913              7258061, 311861, -30594991, -7379421},
2914             {-3773428, -1565936, 28985340, 7499440, 24445838, 9325937, 29727763,
2915              16527196, 18278453, 15405622},
2916             {-4381906, 8508652, -19898366, -3674424, -5984453, 15149970,
2917              -13313598, 843523, -21875062, 13626197},
2918         },
2919         {
2920             {2281448, -13487055, -10915418, -2609910, 1879358, 16164207,
2921              -10783882, 3953792, 13340839, 15928663},
2922             {31727126, -7179855, -18437503, -8283652, 2875793, -16390330,
2923              -25269894, -7014826, -23452306, 5964753},
2924             {4100420, -5959452, -17179337, 6017714, -18705837, 12227141,
2925              -26684835, 11344144, 2538215, -7570755},
2926         },
2927         {
2928             {-9433605, 6123113, 11159803, -2156608, 30016280, 14966241,
2929              -20474983, 1485421, -629256, -15958862},
2930             {-26804558, 4260919, 11851389, 9658551, -32017107, 16367492,
2931              -20205425, -13191288, 11659922, -11115118},
2932             {26180396, 10015009, -30844224, -8581293, 5418197, 9480663, 2231568,
2933              -10170080, 33100372, -1306171},
2934         },
2935         {
2936             {15121113, -5201871, -10389905, 15427821, -27509937, -15992507,
2937              21670947, 4486675, -5931810, -14466380},
2938             {16166486, -9483733, -11104130, 6023908, -31926798, -1364923,
2939              2340060, -16254968, -10735770, -10039824},
2940             {28042865, -3557089, -12126526, 12259706, -3717498, -6945899,
2941              6766453, -8689599, 18036436, 5803270},
2942         },
2943     },
2944     {
2945         {
2946             {-817581, 6763912, 11803561, 1585585, 10958447, -2671165, 23855391,
2947              4598332, -6159431, -14117438},
2948             {-31031306, -14256194, 17332029, -2383520, 31312682, -5967183,
2949              696309, 50292, -20095739, 11763584},
2950             {-594563, -2514283, -32234153, 12643980, 12650761, 14811489, 665117,
2951              -12613632, -19773211, -10713562},
2952         },
2953         {
2954             {30464590, -11262872, -4127476, -12734478, 19835327, -7105613,
2955              -24396175, 2075773, -17020157, 992471},
2956             {18357185, -6994433, 7766382, 16342475, -29324918, 411174, 14578841,
2957              8080033, -11574335, -10601610},
2958             {19598397, 10334610, 12555054, 2555664, 18821899, -10339780,
2959              21873263, 16014234, 26224780, 16452269},
2960         },
2961         {
2962             {-30223925, 5145196, 5944548, 16385966, 3976735, 2009897, -11377804,
2963              -7618186, -20533829, 3698650},
2964             {14187449, 3448569, -10636236, -10810935, -22663880, -3433596,
2965              7268410, -10890444, 27394301, 12015369},
2966             {19695761, 16087646, 28032085, 12999827, 6817792, 11427614,
2967              20244189, -1312777, -13259127, -3402461},
2968         },
2969         {
2970             {30860103, 12735208, -1888245, -4699734, -16974906, 2256940,
2971              -8166013, 12298312, -8550524, -10393462},
2972             {-5719826, -11245325, -1910649, 15569035, 26642876, -7587760,
2973              -5789354, -15118654, -4976164, 12651793},
2974             {-2848395, 9953421, 11531313, -5282879, 26895123, -12697089,
2975              -13118820, -16517902, 9768698, -2533218},
2976         },
2977         {
2978             {-24719459, 1894651, -287698, -4704085, 15348719, -8156530,
2979              32767513, 12765450, 4940095, 10678226},
2980             {18860224, 15980149, -18987240, -1562570, -26233012, -11071856,
2981              -7843882, 13944024, -24372348, 16582019},
2982             {-15504260, 4970268, -29893044, 4175593, -20993212, -2199756,
2983              -11704054, 15444560, -11003761, 7989037},
2984         },
2985         {
2986             {31490452, 5568061, -2412803, 2182383, -32336847, 4531686,
2987              -32078269, 6200206, -19686113, -14800171},
2988             {-17308668, -15879940, -31522777, -2831, -32887382, 16375549,
2989              8680158, -16371713, 28550068, -6857132},
2990             {-28126887, -5688091, 16837845, -1820458, -6850681, 12700016,
2991              -30039981, 4364038, 1155602, 5988841},
2992         },
2993         {
2994             {21890435, -13272907, -12624011, 12154349, -7831873, 15300496,
2995              23148983, -4470481, 24618407, 8283181},
2996             {-33136107, -10512751, 9975416, 6841041, -31559793, 16356536,
2997              3070187, -7025928, 1466169, 10740210},
2998             {-1509399, -15488185, -13503385, -10655916, 32799044, 909394,
2999              -13938903, -5779719, -32164649, -15327040},
3000         },
3001         {
3002             {3960823, -14267803, -28026090, -15918051, -19404858, 13146868,
3003              15567327, 951507, -3260321, -573935},
3004             {24740841, 5052253, -30094131, 8961361, 25877428, 6165135,
3005              -24368180, 14397372, -7380369, -6144105},
3006             {-28888365, 3510803, -28103278, -1158478, -11238128, -10631454,
3007              -15441463, -14453128, -1625486, -6494814},
3008         },
3009     },
3010     {
3011         {
3012             {793299, -9230478, 8836302, -6235707, -27360908, -2369593, 33152843,
3013              -4885251, -9906200, -621852},
3014             {5666233, 525582, 20782575, -8038419, -24538499, 14657740, 16099374,
3015              1468826, -6171428, -15186581},
3016             {-4859255, -3779343, -2917758, -6748019, 7778750, 11688288,
3017              -30404353, -9871238, -1558923, -9863646},
3018         },
3019         {
3020             {10896332, -7719704, 824275, 472601, -19460308, 3009587, 25248958,
3021              14783338, -30581476, -15757844},
3022             {10566929, 12612572, -31944212, 11118703, -12633376, 12362879,
3023              21752402, 8822496, 24003793, 14264025},
3024             {27713862, -7355973, -11008240, 9227530, 27050101, 2504721,
3025              23886875, -13117525, 13958495, -5732453},
3026         },
3027         {
3028             {-23481610, 4867226, -27247128, 3900521, 29838369, -8212291,
3029              -31889399, -10041781, 7340521, -15410068},
3030             {4646514, -8011124, -22766023, -11532654, 23184553, 8566613,
3031              31366726, -1381061, -15066784, -10375192},
3032             {-17270517, 12723032, -16993061, 14878794, 21619651, -6197576,
3033              27584817, 3093888, -8843694, 3849921},
3034         },
3035         {
3036             {-9064912, 2103172, 25561640, -15125738, -5239824, 9582958,
3037              32477045, -9017955, 5002294, -15550259},
3038             {-12057553, -11177906, 21115585, -13365155, 8808712, -12030708,
3039              16489530, 13378448, -25845716, 12741426},
3040             {-5946367, 10645103, -30911586, 15390284, -3286982, -7118677,
3041              24306472, 15852464, 28834118, -7646072},
3042         },
3043         {
3044             {-17335748, -9107057, -24531279, 9434953, -8472084, -583362,
3045              -13090771, 455841, 20461858, 5491305},
3046             {13669248, -16095482, -12481974, -10203039, -14569770, -11893198,
3047              -24995986, 11293807, -28588204, -9421832},
3048             {28497928, 6272777, -33022994, 14470570, 8906179, -1225630,
3049              18504674, -14165166, 29867745, -8795943},
3050         },
3051         {
3052             {-16207023, 13517196, -27799630, -13697798, 24009064, -6373891,
3053              -6367600, -13175392, 22853429, -4012011},
3054             {24191378, 16712145, -13931797, 15217831, 14542237, 1646131,
3055              18603514, -11037887, 12876623, -2112447},
3056             {17902668, 4518229, -411702, -2829247, 26878217, 5258055, -12860753,
3057              608397, 16031844, 3723494},
3058         },
3059         {
3060             {-28632773, 12763728, -20446446, 7577504, 33001348, -13017745,
3061              17558842, -7872890, 23896954, -4314245},
3062             {-20005381, -12011952, 31520464, 605201, 2543521, 5991821, -2945064,
3063              7229064, -9919646, -8826859},
3064             {28816045, 298879, -28165016, -15920938, 19000928, -1665890,
3065              -12680833, -2949325, -18051778, -2082915},
3066         },
3067         {
3068             {16000882, -344896, 3493092, -11447198, -29504595, -13159789,
3069              12577740, 16041268, -19715240, 7847707},
3070             {10151868, 10572098, 27312476, 7922682, 14825339, 4723128,
3071              -32855931, -6519018, -10020567, 3852848},
3072             {-11430470, 15697596, -21121557, -4420647, 5386314, 15063598,
3073              16514493, -15932110, 29330899, -15076224},
3074         },
3075     },
3076     {
3077         {
3078             {-25499735, -4378794, -15222908, -6901211, 16615731, 2051784,
3079              3303702, 15490, -27548796, 12314391},
3080             {15683520, -6003043, 18109120, -9980648, 15337968, -5997823,
3081              -16717435, 15921866, 16103996, -3731215},
3082             {-23169824, -10781249, 13588192, -1628807, -3798557, -1074929,
3083              -19273607, 5402699, -29815713, -9841101},
3084         },
3085         {
3086             {23190676, 2384583, -32714340, 3462154, -29903655, -1529132,
3087              -11266856, 8911517, -25205859, 2739713},
3088             {21374101, -3554250, -33524649, 9874411, 15377179, 11831242,
3089              -33529904, 6134907, 4931255, 11987849},
3090             {-7732, -2978858, -16223486, 7277597, 105524, -322051, -31480539,
3091              13861388, -30076310, 10117930},
3092         },
3093         {
3094             {-29501170, -10744872, -26163768, 13051539, -25625564, 5089643,
3095              -6325503, 6704079, 12890019, 15728940},
3096             {-21972360, -11771379, -951059, -4418840, 14704840, 2695116, 903376,
3097              -10428139, 12885167, 8311031},
3098             {-17516482, 5352194, 10384213, -13811658, 7506451, 13453191,
3099              26423267, 4384730, 1888765, -5435404},
3100         },
3101         {
3102             {-25817338, -3107312, -13494599, -3182506, 30896459, -13921729,
3103              -32251644, -12707869, -19464434, -3340243},
3104             {-23607977, -2665774, -526091, 4651136, 5765089, 4618330, 6092245,
3105              14845197, 17151279, -9854116},
3106             {-24830458, -12733720, -15165978, 10367250, -29530908, -265356,
3107              22825805, -7087279, -16866484, 16176525},
3108         },
3109         {
3110             {-23583256, 6564961, 20063689, 3798228, -4740178, 7359225, 2006182,
3111              -10363426, -28746253, -10197509},
3112             {-10626600, -4486402, -13320562, -5125317, 3432136, -6393229,
3113              23632037, -1940610, 32808310, 1099883},
3114             {15030977, 5768825, -27451236, -2887299, -6427378, -15361371,
3115              -15277896, -6809350, 2051441, -15225865},
3116         },
3117         {
3118             {-3362323, -7239372, 7517890, 9824992, 23555850, 295369, 5148398,
3119              -14154188, -22686354, 16633660},
3120             {4577086, -16752288, 13249841, -15304328, 19958763, -14537274,
3121              18559670, -10759549, 8402478, -9864273},
3122             {-28406330, -1051581, -26790155, -907698, -17212414, -11030789,
3123              9453451, -14980072, 17983010, 9967138},
3124         },
3125         {
3126             {-25762494, 6524722, 26585488, 9969270, 24709298, 1220360, -1677990,
3127              7806337, 17507396, 3651560},
3128             {-10420457, -4118111, 14584639, 15971087, -15768321, 8861010,
3129              26556809, -5574557, -18553322, -11357135},
3130             {2839101, 14284142, 4029895, 3472686, 14402957, 12689363, -26642121,
3131              8459447, -5605463, -7621941},
3132         },
3133         {
3134             {-4839289, -3535444, 9744961, 2871048, 25113978, 3187018, -25110813,
3135              -849066, 17258084, -7977739},
3136             {18164541, -10595176, -17154882, -1542417, 19237078, -9745295,
3137              23357533, -15217008, 26908270, 12150756},
3138             {-30264870, -7647865, 5112249, -7036672, -1499807, -6974257, 43168,
3139              -5537701, -32302074, 16215819},
3140         },
3141     },
3142     {
3143         {
3144             {-6898905, 9824394, -12304779, -4401089, -31397141, -6276835,
3145              32574489, 12532905, -7503072, -8675347},
3146             {-27343522, -16515468, -27151524, -10722951, 946346, 16291093,
3147              254968, 7168080, 21676107, -1943028},
3148             {21260961, -8424752, -16831886, -11920822, -23677961, 3968121,
3149              -3651949, -6215466, -3556191, -7913075},
3150         },
3151         {
3152             {16544754, 13250366, -16804428, 15546242, -4583003, 12757258,
3153              -2462308, -8680336, -18907032, -9662799},
3154             {-2415239, -15577728, 18312303, 4964443, -15272530, -12653564,
3155              26820651, 16690659, 25459437, -4564609},
3156             {-25144690, 11425020, 28423002, -11020557, -6144921, -15826224,
3157              9142795, -2391602, -6432418, -1644817},
3158         },
3159         {
3160             {-23104652, 6253476, 16964147, -3768872, -25113972, -12296437,
3161              -27457225, -16344658, 6335692, 7249989},
3162             {-30333227, 13979675, 7503222, -12368314, -11956721, -4621693,
3163              -30272269, 2682242, 25993170, -12478523},
3164             {4364628, 5930691, 32304656, -10044554, -8054781, 15091131,
3165              22857016, -10598955, 31820368, 15075278},
3166         },
3167         {
3168             {31879134, -8918693, 17258761, 90626, -8041836, -4917709, 24162788,
3169              -9650886, -17970238, 12833045},
3170             {19073683, 14851414, -24403169, -11860168, 7625278, 11091125,
3171              -19619190, 2074449, -9413939, 14905377},
3172             {24483667, -11935567, -2518866, -11547418, -1553130, 15355506,
3173              -25282080, 9253129, 27628530, -7555480},
3174         },
3175         {
3176             {17597607, 8340603, 19355617, 552187, 26198470, -3176583, 4593324,
3177              -9157582, -14110875, 15297016},
3178             {510886, 14337390, -31785257, 16638632, 6328095, 2713355, -20217417,
3179              -11864220, 8683221, 2921426},
3180             {18606791, 11874196, 27155355, -5281482, -24031742, 6265446,
3181              -25178240, -1278924, 4674690, 13890525},
3182         },
3183         {
3184             {13609624, 13069022, -27372361, -13055908, 24360586, 9592974,
3185              14977157, 9835105, 4389687, 288396},
3186             {9922506, -519394, 13613107, 5883594, -18758345, -434263, -12304062,
3187              8317628, 23388070, 16052080},
3188             {12720016, 11937594, -31970060, -5028689, 26900120, 8561328,
3189              -20155687, -11632979, -14754271, -10812892},
3190         },
3191         {
3192             {15961858, 14150409, 26716931, -665832, -22794328, 13603569,
3193              11829573, 7467844, -28822128, 929275},
3194             {11038231, -11582396, -27310482, -7316562, -10498527, -16307831,
3195              -23479533, -9371869, -21393143, 2465074},
3196             {20017163, -4323226, 27915242, 1529148, 12396362, 15675764,
3197              13817261, -9658066, 2463391, -4622140},
3198         },
3199         {
3200             {-16358878, -12663911, -12065183, 4996454, -1256422, 1073572,
3201              9583558, 12851107, 4003896, 12673717},
3202             {-1731589, -15155870, -3262930, 16143082, 19294135, 13385325,
3203              14741514, -9103726, 7903886, 2348101},
3204             {24536016, -16515207, 12715592, -3862155, 1511293, 10047386,
3205              -3842346, -7129159, -28377538, 10048127},
3206         },
3207     },
3208     {
3209         {
3210             {-12622226, -6204820, 30718825, 2591312, -10617028, 12192840,
3211              18873298, -7297090, -32297756, 15221632},
3212             {-26478122, -11103864, 11546244, -1852483, 9180880, 7656409,
3213              -21343950, 2095755, 29769758, 6593415},
3214             {-31994208, -2907461, 4176912, 3264766, 12538965, -868111, 26312345,
3215              -6118678, 30958054, 8292160},
3216         },
3217         {
3218             {31429822, -13959116, 29173532, 15632448, 12174511, -2760094,
3219              32808831, 3977186, 26143136, -3148876},
3220             {22648901, 1402143, -22799984, 13746059, 7936347, 365344, -8668633,
3221              -1674433, -3758243, -2304625},
3222             {-15491917, 8012313, -2514730, -12702462, -23965846, -10254029,
3223              -1612713, -1535569, -16664475, 8194478},
3224         },
3225         {
3226             {27338066, -7507420, -7414224, 10140405, -19026427, -6589889,
3227              27277191, 8855376, 28572286, 3005164},
3228             {26287124, 4821776, 25476601, -4145903, -3764513, -15788984,
3229              -18008582, 1182479, -26094821, -13079595},
3230             {-7171154, 3178080, 23970071, 6201893, -17195577, -4489192,
3231              -21876275, -13982627, 32208683, -1198248},
3232         },
3233         {
3234             {-16657702, 2817643, -10286362, 14811298, 6024667, 13349505,
3235              -27315504, -10497842, -27672585, -11539858},
3236             {15941029, -9405932, -21367050, 8062055, 31876073, -238629,
3237              -15278393, -1444429, 15397331, -4130193},
3238             {8934485, -13485467, -23286397, -13423241, -32446090, 14047986,
3239              31170398, -1441021, -27505566, 15087184},
3240         },
3241         {
3242             {-18357243, -2156491, 24524913, -16677868, 15520427, -6360776,
3243              -15502406, 11461896, 16788528, -5868942},
3244             {-1947386, 16013773, 21750665, 3714552, -17401782, -16055433,
3245              -3770287, -10323320, 31322514, -11615635},
3246             {21426655, -5650218, -13648287, -5347537, -28812189, -4920970,
3247              -18275391, -14621414, 13040862, -12112948},
3248         },
3249         {
3250             {11293895, 12478086, -27136401, 15083750, -29307421, 14748872,
3251              14555558, -13417103, 1613711, 4896935},
3252             {-25894883, 15323294, -8489791, -8057900, 25967126, -13425460,
3253              2825960, -4897045, -23971776, -11267415},
3254             {-15924766, -5229880, -17443532, 6410664, 3622847, 10243618,
3255              20615400, 12405433, -23753030, -8436416},
3256         },
3257         {
3258             {-7091295, 12556208, -20191352, 9025187, -17072479, 4333801,
3259              4378436, 2432030, 23097949, -566018},
3260             {4565804, -16025654, 20084412, -7842817, 1724999, 189254, 24767264,
3261              10103221, -18512313, 2424778},
3262             {366633, -11976806, 8173090, -6890119, 30788634, 5745705, -7168678,
3263              1344109, -3642553, 12412659},
3264         },
3265         {
3266             {-24001791, 7690286, 14929416, -168257, -32210835, -13412986,
3267              24162697, -15326504, -3141501, 11179385},
3268             {18289522, -14724954, 8056945, 16430056, -21729724, 7842514,
3269              -6001441, -1486897, -18684645, -11443503},
3270             {476239, 6601091, -6152790, -9723375, 17503545, -4863900, 27672959,
3271              13403813, 11052904, 5219329},
3272         },
3273     },
3274     {
3275         {
3276             {20678546, -8375738, -32671898, 8849123, -5009758, 14574752,
3277              31186971, -3973730, 9014762, -8579056},
3278             {-13644050, -10350239, -15962508, 5075808, -1514661, -11534600,
3279              -33102500, 9160280, 8473550, -3256838},
3280             {24900749, 14435722, 17209120, -15292541, -22592275, 9878983,
3281              -7689309, -16335821, -24568481, 11788948},
3282         },
3283         {
3284             {-3118155, -11395194, -13802089, 14797441, 9652448, -6845904,
3285              -20037437, 10410733, -24568470, -1458691},
3286             {-15659161, 16736706, -22467150, 10215878, -9097177, 7563911,
3287              11871841, -12505194, -18513325, 8464118},
3288             {-23400612, 8348507, -14585951, -861714, -3950205, -6373419,
3289              14325289, 8628612, 33313881, -8370517},
3290         },
3291         {
3292             {-20186973, -4967935, 22367356, 5271547, -1097117, -4788838,
3293              -24805667, -10236854, -8940735, -5818269},
3294             {-6948785, -1795212, -32625683, -16021179, 32635414, -7374245,
3295              15989197, -12838188, 28358192, -4253904},
3296             {-23561781, -2799059, -32351682, -1661963, -9147719, 10429267,
3297              -16637684, 4072016, -5351664, 5596589},
3298         },
3299         {
3300             {-28236598, -3390048, 12312896, 6213178, 3117142, 16078565,
3301              29266239, 2557221, 1768301, 15373193},
3302             {-7243358, -3246960, -4593467, -7553353, -127927, -912245, -1090902,
3303              -4504991, -24660491, 3442910},
3304             {-30210571, 5124043, 14181784, 8197961, 18964734, -11939093,
3305              22597931, 7176455, -18585478, 13365930},
3306         },
3307         {
3308             {-7877390, -1499958, 8324673, 4690079, 6261860, 890446, 24538107,
3309              -8570186, -9689599, -3031667},
3310             {25008904, -10771599, -4305031, -9638010, 16265036, 15721635,
3311              683793, -11823784, 15723479, -15163481},
3312             {-9660625, 12374379, -27006999, -7026148, -7724114, -12314514,
3313              11879682, 5400171, 519526, -1235876},
3314         },
3315         {
3316             {22258397, -16332233, -7869817, 14613016, -22520255, -2950923,
3317              -20353881, 7315967, 16648397, 7605640},
3318             {-8081308, -8464597, -8223311, 9719710, 19259459, -15348212,
3319              23994942, -5281555, -9468848, 4763278},
3320             {-21699244, 9220969, -15730624, 1084137, -25476107, -2852390,
3321              31088447, -7764523, -11356529, 728112},
3322         },
3323         {
3324             {26047220, -11751471, -6900323, -16521798, 24092068, 9158119,
3325              -4273545, -12555558, -29365436, -5498272},
3326             {17510331, -322857, 5854289, 8403524, 17133918, -3112612, -28111007,
3327              12327945, 10750447, 10014012},
3328             {-10312768, 3936952, 9156313, -8897683, 16498692, -994647,
3329              -27481051, -666732, 3424691, 7540221},
3330         },
3331         {
3332             {30322361, -6964110, 11361005, -4143317, 7433304, 4989748, -7071422,
3333              -16317219, -9244265, 15258046},
3334             {13054562, -2779497, 19155474, 469045, -12482797, 4566042, 5631406,
3335              2711395, 1062915, -5136345},
3336             {-19240248, -11254599, -29509029, -7499965, -5835763, 13005411,
3337              -6066489, 12194497, 32960380, 1459310},
3338         },
3339     },
3340     {
3341         {
3342             {19852034, 7027924, 23669353, 10020366, 8586503, -6657907, 394197,
3343              -6101885, 18638003, -11174937},
3344             {31395534, 15098109, 26581030, 8030562, -16527914, -5007134,
3345              9012486, -7584354, -6643087, -5442636},
3346             {-9192165, -2347377, -1997099, 4529534, 25766844, 607986, -13222,
3347              9677543, -32294889, -6456008},
3348         },
3349         {
3350             {-2444496, -149937, 29348902, 8186665, 1873760, 12489863, -30934579,
3351              -7839692, -7852844, -8138429},
3352             {-15236356, -15433509, 7766470, 746860, 26346930, -10221762,
3353              -27333451, 10754588, -9431476, 5203576},
3354             {31834314, 14135496, -770007, 5159118, 20917671, -16768096,
3355              -7467973, -7337524, 31809243, 7347066},
3356         },
3357         {
3358             {-9606723, -11874240, 20414459, 13033986, 13716524, -11691881,
3359              19797970, -12211255, 15192876, -2087490},
3360             {-12663563, -2181719, 1168162, -3804809, 26747877, -14138091,
3361              10609330, 12694420, 33473243, -13382104},
3362             {33184999, 11180355, 15832085, -11385430, -1633671, 225884,
3363              15089336, -11023903, -6135662, 14480053},
3364         },
3365         {
3366             {31308717, -5619998, 31030840, -1897099, 15674547, -6582883,
3367              5496208, 13685227, 27595050, 8737275},
3368             {-20318852, -15150239, 10933843, -16178022, 8335352, -7546022,
3369              -31008351, -12610604, 26498114, 66511},
3370             {22644454, -8761729, -16671776, 4884562, -3105614, -13559366,
3371              30540766, -4286747, -13327787, -7515095},
3372         },
3373         {
3374             {-28017847, 9834845, 18617207, -2681312, -3401956, -13307506,
3375              8205540, 13585437, -17127465, 15115439},
3376             {23711543, -672915, 31206561, -8362711, 6164647, -9709987,
3377              -33535882, -1426096, 8236921, 16492939},
3378             {-23910559, -13515526, -26299483, -4503841, 25005590, -7687270,
3379              19574902, 10071562, 6708380, -6222424},
3380         },
3381         {
3382             {2101391, -4930054, 19702731, 2367575, -15427167, 1047675, 5301017,
3383              9328700, 29955601, -11678310},
3384             {3096359, 9271816, -21620864, -15521844, -14847996, -7592937,
3385              -25892142, -12635595, -9917575, 6216608},
3386             {-32615849, 338663, -25195611, 2510422, -29213566, -13820213,
3387              24822830, -6146567, -26767480, 7525079},
3388         },
3389         {
3390             {-23066649, -13985623, 16133487, -7896178, -3389565, 778788,
3391              -910336, -2782495, -19386633, 11994101},
3392             {21691500, -13624626, -641331, -14367021, 3285881, -3483596,
3393              -25064666, 9718258, -7477437, 13381418},
3394             {18445390, -4202236, 14979846, 11622458, -1727110, -3582980,
3395              23111648, -6375247, 28535282, 15779576},
3396         },
3397         {
3398             {30098053, 3089662, -9234387, 16662135, -21306940, 11308411,
3399              -14068454, 12021730, 9955285, -16303356},
3400             {9734894, -14576830, -7473633, -9138735, 2060392, 11313496,
3401              -18426029, 9924399, 20194861, 13380996},
3402             {-26378102, -7965207, -22167821, 15789297, -18055342, -6168792,
3403              -1984914, 15707771, 26342023, 10146099},
3404         },
3405     },
3406     {
3407         {
3408             {-26016874, -219943, 21339191, -41388, 19745256, -2878700,
3409              -29637280, 2227040, 21612326, -545728},
3410             {-13077387, 1184228, 23562814, -5970442, -20351244, -6348714,
3411              25764461, 12243797, -20856566, 11649658},
3412             {-10031494, 11262626, 27384172, 2271902, 26947504, -15997771, 39944,
3413              6114064, 33514190, 2333242},
3414         },
3415         {
3416             {-21433588, -12421821, 8119782, 7219913, -21830522, -9016134,
3417              -6679750, -12670638, 24350578, -13450001},
3418             {-4116307, -11271533, -23886186, 4843615, -30088339, 690623,
3419              -31536088, -10406836, 8317860, 12352766},
3420             {18200138, -14475911, -33087759, -2696619, -23702521, -9102511,
3421              -23552096, -2287550, 20712163, 6719373},
3422         },
3423         {
3424             {26656208, 6075253, -7858556, 1886072, -28344043, 4262326, 11117530,
3425              -3763210, 26224235, -3297458},
3426             {-17168938, -14854097, -3395676, -16369877, -19954045, 14050420,
3427              21728352, 9493610, 18620611, -16428628},
3428             {-13323321, 13325349, 11432106, 5964811, 18609221, 6062965,
3429              -5269471, -9725556, -30701573, -16479657},
3430         },
3431         {
3432             {-23860538, -11233159, 26961357, 1640861, -32413112, -16737940,
3433              12248509, -5240639, 13735342, 1934062},
3434             {25089769, 6742589, 17081145, -13406266, 21909293, -16067981,
3435              -15136294, -3765346, -21277997, 5473616},
3436             {31883677, -7961101, 1083432, -11572403, 22828471, 13290673,
3437              -7125085, 12469656, 29111212, -5451014},
3438         },
3439         {
3440             {24244947, -15050407, -26262976, 2791540, -14997599, 16666678,
3441              24367466, 6388839, -10295587, 452383},
3442             {-25640782, -3417841, 5217916, 16224624, 19987036, -4082269,
3443              -24236251, -5915248, 15766062, 8407814},
3444             {-20406999, 13990231, 15495425, 16395525, 5377168, 15166495,
3445              -8917023, -4388953, -8067909, 2276718},
3446         },
3447         {
3448             {30157918, 12924066, -17712050, 9245753, 19895028, 3368142,
3449              -23827587, 5096219, 22740376, -7303417},
3450             {2041139, -14256350, 7783687, 13876377, -25946985, -13352459,
3451              24051124, 13742383, -15637599, 13295222},
3452             {33338237, -8505733, 12532113, 7977527, 9106186, -1715251,
3453              -17720195, -4612972, -4451357, -14669444},
3454         },
3455         {
3456             {-20045281, 5454097, -14346548, 6447146, 28862071, 1883651,
3457              -2469266, -4141880, 7770569, 9620597},
3458             {23208068, 7979712, 33071466, 8149229, 1758231, -10834995, 30945528,
3459              -1694323, -33502340, -14767970},
3460             {1439958, -16270480, -1079989, -793782, 4625402, 10647766, -5043801,
3461              1220118, 30494170, -11440799},
3462         },
3463         {
3464             {-5037580, -13028295, -2970559, -3061767, 15640974, -6701666,
3465              -26739026, 926050, -1684339, -13333647},
3466             {13908495, -3549272, 30919928, -6273825, -21521863, 7989039,
3467              9021034, 9078865, 3353509, 4033511},
3468             {-29663431, -15113610, 32259991, -344482, 24295849, -12912123,
3469              23161163, 8839127, 27485041, 7356032},
3470         },
3471     },
3472     {
3473         {
3474             {9661027, 705443, 11980065, -5370154, -1628543, 14661173, -6346142,
3475              2625015, 28431036, -16771834},
3476             {-23839233, -8311415, -25945511, 7480958, -17681669, -8354183,
3477              -22545972, 14150565, 15970762, 4099461},
3478             {29262576, 16756590, 26350592, -8793563, 8529671, -11208050,
3479              13617293, -9937143, 11465739, 8317062},
3480         },
3481         {
3482             {-25493081, -6962928, 32500200, -9419051, -23038724, -2302222,
3483              14898637, 3848455, 20969334, -5157516},
3484             {-20384450, -14347713, -18336405, 13884722, -33039454, 2842114,
3485              -21610826, -3649888, 11177095, 14989547},
3486             {-24496721, -11716016, 16959896, 2278463, 12066309, 10137771,
3487              13515641, 2581286, -28487508, 9930240},
3488         },
3489         {
3490             {-17751622, -2097826, 16544300, -13009300, -15914807, -14949081,
3491              18345767, -13403753, 16291481, -5314038},
3492             {-33229194, 2553288, 32678213, 9875984, 8534129, 6889387, -9676774,
3493              6957617, 4368891, 9788741},
3494             {16660756, 7281060, -10830758, 12911820, 20108584, -8101676,
3495              -21722536, -8613148, 16250552, -11111103},
3496         },
3497         {
3498             {-19765507, 2390526, -16551031, 14161980, 1905286, 6414907, 4689584,
3499              10604807, -30190403, 4782747},
3500             {-1354539, 14736941, -7367442, -13292886, 7710542, -14155590,
3501              -9981571, 4383045, 22546403, 437323},
3502             {31665577, -12180464, -16186830, 1491339, -18368625, 3294682,
3503              27343084, 2786261, -30633590, -14097016},
3504         },
3505         {
3506             {-14467279, -683715, -33374107, 7448552, 19294360, 14334329,
3507              -19690631, 2355319, -19284671, -6114373},
3508             {15121312, -15796162, 6377020, -6031361, -10798111, -12957845,
3509              18952177, 15496498, -29380133, 11754228},
3510             {-2637277, -13483075, 8488727, -14303896, 12728761, -1622493,
3511              7141596, 11724556, 22761615, -10134141},
3512         },
3513         {
3514             {16918416, 11729663, -18083579, 3022987, -31015732, -13339659,
3515              -28741185, -12227393, 32851222, 11717399},
3516             {11166634, 7338049, -6722523, 4531520, -29468672, -7302055,
3517              31474879, 3483633, -1193175, -4030831},
3518             {-185635, 9921305, 31456609, -13536438, -12013818, 13348923,
3519              33142652, 6546660, -19985279, -3948376},
3520         },
3521         {
3522             {-32460596, 11266712, -11197107, -7899103, 31703694, 3855903,
3523              -8537131, -12833048, -30772034, -15486313},
3524             {-18006477, 12709068, 3991746, -6479188, -21491523, -10550425,
3525              -31135347, -16049879, 10928917, 3011958},
3526             {-6957757, -15594337, 31696059, 334240, 29576716, 14796075,
3527              -30831056, -12805180, 18008031, 10258577},
3528         },
3529         {
3530             {-22448644, 15655569, 7018479, -4410003, -30314266, -1201591,
3531              -1853465, 1367120, 25127874, 6671743},
3532             {29701166, -14373934, -10878120, 9279288, -17568, 13127210,
3533              21382910, 11042292, 25838796, 4642684},
3534             {-20430234, 14955537, -24126347, 8124619, -5369288, -5990470,
3535              30468147, -13900640, 18423289, 4177476},
3536         },
3537     },
3538 };
3539
3540 static uint8_t negative(signed char b) {
3541   uint32_t x = b;
3542   x >>= 31; /* 1: yes; 0: no */
3543   return x;
3544 }
3545
3546 static void table_select(ge_precomp *t, int pos, signed char b) {
3547   ge_precomp minust;
3548   uint8_t bnegative = negative(b);
3549   uint8_t babs = b - (((-bnegative) & b) << 1);
3550
3551   ge_precomp_0(t);
3552   cmov(t, &k25519Precomp[pos][0], equal(babs, 1));
3553   cmov(t, &k25519Precomp[pos][1], equal(babs, 2));
3554   cmov(t, &k25519Precomp[pos][2], equal(babs, 3));
3555   cmov(t, &k25519Precomp[pos][3], equal(babs, 4));
3556   cmov(t, &k25519Precomp[pos][4], equal(babs, 5));
3557   cmov(t, &k25519Precomp[pos][5], equal(babs, 6));
3558   cmov(t, &k25519Precomp[pos][6], equal(babs, 7));
3559   cmov(t, &k25519Precomp[pos][7], equal(babs, 8));
3560   fe_copy(minust.yplusx, t->yminusx);
3561   fe_copy(minust.yminusx, t->yplusx);
3562   fe_neg(minust.xy2d, t->xy2d);
3563   cmov(t, &minust, bnegative);
3564 }
3565
3566 /* h = a * B
3567  * where a = a[0]+256*a[1]+...+256^31 a[31]
3568  * B is the Ed25519 base point (x,4/5) with x positive.
3569  *
3570  * Preconditions:
3571  *   a[31] <= 127 */
3572 static void ge_scalarmult_base(ge_p3 *h, const uint8_t *a) {
3573   signed char e[64];
3574   signed char carry;
3575   ge_p1p1 r;
3576   ge_p2 s;
3577   ge_precomp t;
3578   int i;
3579
3580   for (i = 0; i < 32; ++i) {
3581     e[2 * i + 0] = (a[i] >> 0) & 15;
3582     e[2 * i + 1] = (a[i] >> 4) & 15;
3583   }
3584   /* each e[i] is between 0 and 15 */
3585   /* e[63] is between 0 and 7 */
3586
3587   carry = 0;
3588   for (i = 0; i < 63; ++i) {
3589     e[i] += carry;
3590     carry = e[i] + 8;
3591     carry >>= 4;
3592     e[i] -= carry << 4;
3593   }
3594   e[63] += carry;
3595   /* each e[i] is between -8 and 8 */
3596
3597   ge_p3_0(h);
3598   for (i = 1; i < 64; i += 2) {
3599     table_select(&t, i / 2, e[i]);
3600     ge_madd(&r, h, &t);
3601     ge_p1p1_to_p3(h, &r);
3602   }
3603
3604   ge_p3_dbl(&r, h);
3605   ge_p1p1_to_p2(&s, &r);
3606   ge_p2_dbl(&r, &s);
3607   ge_p1p1_to_p2(&s, &r);
3608   ge_p2_dbl(&r, &s);
3609   ge_p1p1_to_p2(&s, &r);
3610   ge_p2_dbl(&r, &s);
3611   ge_p1p1_to_p3(h, &r);
3612
3613   for (i = 0; i < 64; i += 2) {
3614     table_select(&t, i / 2, e[i]);
3615     ge_madd(&r, h, &t);
3616     ge_p1p1_to_p3(h, &r);
3617   }
3618 }
3619
3620 #endif
3621
3622 static void slide(signed char *r, const uint8_t *a) {
3623   int i;
3624   int b;
3625   int k;
3626
3627   for (i = 0; i < 256; ++i) {
3628     r[i] = 1 & (a[i >> 3] >> (i & 7));
3629   }
3630
3631   for (i = 0; i < 256; ++i) {
3632     if (r[i]) {
3633       for (b = 1; b <= 6 && i + b < 256; ++b) {
3634         if (r[i + b]) {
3635           if (r[i] + (r[i + b] << b) <= 15) {
3636             r[i] += r[i + b] << b;
3637             r[i + b] = 0;
3638           } else if (r[i] - (r[i + b] << b) >= -15) {
3639             r[i] -= r[i + b] << b;
3640             for (k = i + b; k < 256; ++k) {
3641               if (!r[k]) {
3642                 r[k] = 1;
3643                 break;
3644               }
3645               r[k] = 0;
3646             }
3647           } else {
3648             break;
3649           }
3650         }
3651       }
3652     }
3653   }
3654 }
3655
3656 static ge_precomp Bi[8] = {
3657     {
3658         {25967493, -14356035, 29566456, 3660896, -12694345, 4014787, 27544626,
3659          -11754271, -6079156, 2047605},
3660         {-12545711, 934262, -2722910, 3049990, -727428, 9406986, 12720692,
3661          5043384, 19500929, -15469378},
3662         {-8738181, 4489570, 9688441, -14785194, 10184609, -12363380, 29287919,
3663          11864899, -24514362, -4438546},
3664     },
3665     {
3666         {15636291, -9688557, 24204773, -7912398, 616977, -16685262, 27787600,
3667          -14772189, 28944400, -1550024},
3668         {16568933, 4717097, -11556148, -1102322, 15682896, -11807043, 16354577,
3669          -11775962, 7689662, 11199574},
3670         {30464156, -5976125, -11779434, -15670865, 23220365, 15915852, 7512774,
3671          10017326, -17749093, -9920357},
3672     },
3673     {
3674         {10861363, 11473154, 27284546, 1981175, -30064349, 12577861, 32867885,
3675          14515107, -15438304, 10819380},
3676         {4708026, 6336745, 20377586, 9066809, -11272109, 6594696, -25653668,
3677          12483688, -12668491, 5581306},
3678         {19563160, 16186464, -29386857, 4097519, 10237984, -4348115, 28542350,
3679          13850243, -23678021, -15815942},
3680     },
3681     {
3682         {5153746, 9909285, 1723747, -2777874, 30523605, 5516873, 19480852,
3683          5230134, -23952439, -15175766},
3684         {-30269007, -3463509, 7665486, 10083793, 28475525, 1649722, 20654025,
3685          16520125, 30598449, 7715701},
3686         {28881845, 14381568, 9657904, 3680757, -20181635, 7843316, -31400660,
3687          1370708, 29794553, -1409300},
3688     },
3689     {
3690         {-22518993, -6692182, 14201702, -8745502, -23510406, 8844726, 18474211,
3691          -1361450, -13062696, 13821877},
3692         {-6455177, -7839871, 3374702, -4740862, -27098617, -10571707, 31655028,
3693          -7212327, 18853322, -14220951},
3694         {4566830, -12963868, -28974889, -12240689, -7602672, -2830569, -8514358,
3695          -10431137, 2207753, -3209784},
3696     },
3697     {
3698         {-25154831, -4185821, 29681144, 7868801, -6854661, -9423865, -12437364,
3699          -663000, -31111463, -16132436},
3700         {25576264, -2703214, 7349804, -11814844, 16472782, 9300885, 3844789,
3701          15725684, 171356, 6466918},
3702         {23103977, 13316479, 9739013, -16149481, 817875, -15038942, 8965339,
3703          -14088058, -30714912, 16193877},
3704     },
3705     {
3706         {-33521811, 3180713, -2394130, 14003687, -16903474, -16270840, 17238398,
3707          4729455, -18074513, 9256800},
3708         {-25182317, -4174131, 32336398, 5036987, -21236817, 11360617, 22616405,
3709          9761698, -19827198, 630305},
3710         {-13720693, 2639453, -24237460, -7406481, 9494427, -5774029, -6554551,
3711          -15960994, -2449256, -14291300},
3712     },
3713     {
3714         {-3151181, -5046075, 9282714, 6866145, -31907062, -863023, -18940575,
3715          15033784, 25105118, -7894876},
3716         {-24326370, 15950226, -31801215, -14592823, -11662737, -5090925,
3717          1573892, -2625887, 2198790, -15804619},
3718         {-3099351, 10324967, -2241613, 7453183, -5446979, -2735503, -13812022,
3719          -16236442, -32461234, -12290683},
3720     },
3721 };
3722
3723 /* r = a * A + b * B
3724  * where a = a[0]+256*a[1]+...+256^31 a[31].
3725  * and b = b[0]+256*b[1]+...+256^31 b[31].
3726  * B is the Ed25519 base point (x,4/5) with x positive. */
3727 void ge_double_scalarmult_vartime(ge_p2 *r, const uint8_t *a,
3728                                   const ge_p3 *A, const uint8_t *b) {
3729   signed char aslide[256];
3730   signed char bslide[256];
3731   ge_cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */
3732   ge_p1p1 t;
3733   ge_p3 u;
3734   ge_p3 A2;
3735   int i;
3736
3737   slide(aslide, a);
3738   slide(bslide, b);
3739
3740   ge_p3_to_cached(&Ai[0], A);
3741   ge_p3_dbl(&t, A);
3742   ge_p1p1_to_p3(&A2, &t);
3743   ge_add(&t, &A2, &Ai[0]);
3744   ge_p1p1_to_p3(&u, &t);
3745   ge_p3_to_cached(&Ai[1], &u);
3746   ge_add(&t, &A2, &Ai[1]);
3747   ge_p1p1_to_p3(&u, &t);
3748   ge_p3_to_cached(&Ai[2], &u);
3749   ge_add(&t, &A2, &Ai[2]);
3750   ge_p1p1_to_p3(&u, &t);
3751   ge_p3_to_cached(&Ai[3], &u);
3752   ge_add(&t, &A2, &Ai[3]);
3753   ge_p1p1_to_p3(&u, &t);
3754   ge_p3_to_cached(&Ai[4], &u);
3755   ge_add(&t, &A2, &Ai[4]);
3756   ge_p1p1_to_p3(&u, &t);
3757   ge_p3_to_cached(&Ai[5], &u);
3758   ge_add(&t, &A2, &Ai[5]);
3759   ge_p1p1_to_p3(&u, &t);
3760   ge_p3_to_cached(&Ai[6], &u);
3761   ge_add(&t, &A2, &Ai[6]);
3762   ge_p1p1_to_p3(&u, &t);
3763   ge_p3_to_cached(&Ai[7], &u);
3764
3765   ge_p2_0(r);
3766
3767   for (i = 255; i >= 0; --i) {
3768     if (aslide[i] || bslide[i]) {
3769       break;
3770     }
3771   }
3772
3773   for (; i >= 0; --i) {
3774     ge_p2_dbl(&t, r);
3775
3776     if (aslide[i] > 0) {
3777       ge_p1p1_to_p3(&u, &t);
3778       ge_add(&t, &u, &Ai[aslide[i] / 2]);
3779     } else if (aslide[i] < 0) {
3780       ge_p1p1_to_p3(&u, &t);
3781       ge_sub(&t, &u, &Ai[(-aslide[i]) / 2]);
3782     }
3783
3784     if (bslide[i] > 0) {
3785       ge_p1p1_to_p3(&u, &t);
3786       ge_madd(&t, &u, &Bi[bslide[i] / 2]);
3787     } else if (bslide[i] < 0) {
3788       ge_p1p1_to_p3(&u, &t);
3789       ge_msub(&t, &u, &Bi[(-bslide[i]) / 2]);
3790     }
3791
3792     ge_p1p1_to_p2(r, &t);
3793   }
3794 }
3795
3796 /* The set of scalars is \Z/l
3797  * where l = 2^252 + 27742317777372353535851937790883648493. */
3798
3799 /* Input:
3800  *   s[0]+256*s[1]+...+256^63*s[63] = s
3801  *
3802  * Output:
3803  *   s[0]+256*s[1]+...+256^31*s[31] = s mod l
3804  *   where l = 2^252 + 27742317777372353535851937790883648493.
3805  *   Overwrites s in place. */
3806 static void sc_reduce(uint8_t *s) {
3807   int64_t s0 = 2097151 & load_3(s);
3808   int64_t s1 = 2097151 & (load_4(s + 2) >> 5);
3809   int64_t s2 = 2097151 & (load_3(s + 5) >> 2);
3810   int64_t s3 = 2097151 & (load_4(s + 7) >> 7);
3811   int64_t s4 = 2097151 & (load_4(s + 10) >> 4);
3812   int64_t s5 = 2097151 & (load_3(s + 13) >> 1);
3813   int64_t s6 = 2097151 & (load_4(s + 15) >> 6);
3814   int64_t s7 = 2097151 & (load_3(s + 18) >> 3);
3815   int64_t s8 = 2097151 & load_3(s + 21);
3816   int64_t s9 = 2097151 & (load_4(s + 23) >> 5);
3817   int64_t s10 = 2097151 & (load_3(s + 26) >> 2);
3818   int64_t s11 = 2097151 & (load_4(s + 28) >> 7);
3819   int64_t s12 = 2097151 & (load_4(s + 31) >> 4);
3820   int64_t s13 = 2097151 & (load_3(s + 34) >> 1);
3821   int64_t s14 = 2097151 & (load_4(s + 36) >> 6);
3822   int64_t s15 = 2097151 & (load_3(s + 39) >> 3);
3823   int64_t s16 = 2097151 & load_3(s + 42);
3824   int64_t s17 = 2097151 & (load_4(s + 44) >> 5);
3825   int64_t s18 = 2097151 & (load_3(s + 47) >> 2);
3826   int64_t s19 = 2097151 & (load_4(s + 49) >> 7);
3827   int64_t s20 = 2097151 & (load_4(s + 52) >> 4);
3828   int64_t s21 = 2097151 & (load_3(s + 55) >> 1);
3829   int64_t s22 = 2097151 & (load_4(s + 57) >> 6);
3830   int64_t s23 = (load_4(s + 60) >> 3);
3831   int64_t carry0;
3832   int64_t carry1;
3833   int64_t carry2;
3834   int64_t carry3;
3835   int64_t carry4;
3836   int64_t carry5;
3837   int64_t carry6;
3838   int64_t carry7;
3839   int64_t carry8;
3840   int64_t carry9;
3841   int64_t carry10;
3842   int64_t carry11;
3843   int64_t carry12;
3844   int64_t carry13;
3845   int64_t carry14;
3846   int64_t carry15;
3847   int64_t carry16;
3848
3849   s11 += s23 * 666643;
3850   s12 += s23 * 470296;
3851   s13 += s23 * 654183;
3852   s14 -= s23 * 997805;
3853   s15 += s23 * 136657;
3854   s16 -= s23 * 683901;
3855   s23 = 0;
3856
3857   s10 += s22 * 666643;
3858   s11 += s22 * 470296;
3859   s12 += s22 * 654183;
3860   s13 -= s22 * 997805;
3861   s14 += s22 * 136657;
3862   s15 -= s22 * 683901;
3863   s22 = 0;
3864
3865   s9 += s21 * 666643;
3866   s10 += s21 * 470296;
3867   s11 += s21 * 654183;
3868   s12 -= s21 * 997805;
3869   s13 += s21 * 136657;
3870   s14 -= s21 * 683901;
3871   s21 = 0;
3872
3873   s8 += s20 * 666643;
3874   s9 += s20 * 470296;
3875   s10 += s20 * 654183;
3876   s11 -= s20 * 997805;
3877   s12 += s20 * 136657;
3878   s13 -= s20 * 683901;
3879   s20 = 0;
3880
3881   s7 += s19 * 666643;
3882   s8 += s19 * 470296;
3883   s9 += s19 * 654183;
3884   s10 -= s19 * 997805;
3885   s11 += s19 * 136657;
3886   s12 -= s19 * 683901;
3887   s19 = 0;
3888
3889   s6 += s18 * 666643;
3890   s7 += s18 * 470296;
3891   s8 += s18 * 654183;
3892   s9 -= s18 * 997805;
3893   s10 += s18 * 136657;
3894   s11 -= s18 * 683901;
3895   s18 = 0;
3896
3897   carry6 = (s6 + (1 << 20)) >> 21;
3898   s7 += carry6;
3899   s6 -= carry6 << 21;
3900   carry8 = (s8 + (1 << 20)) >> 21;
3901  &nb