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