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