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