crypto/ec/curve25519.c

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