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