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