math/f25519.[ch]: More field operations.

Most are fairly simple utilities, except for `f25519_quosqrt' which does
a combined division and square root.

diff --git a/math/f25519.c b/math/f25519.c
index 220a73c..6dfc511 100644 (file)
--- a/math/f25519.c
+++ b/math/f25519.c
@@ -29,6 +29,7 @@
 
 #include "config.h"
 
+#include "ct.h"
 #include "f25519.h"
 
 /*----- Basic setup -------------------------------------------------------*/
@@ -498,8 +499,114 @@ void f25519_sub(f25519 *z, const f25519 *x, const f25519 *y)
 #endif
 }
 
+/* --- @f25519_neg@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@)
+ *             @const f25519 *x@ = an operand
+ *
+ * Returns:    ---
+ *
+ * Use:                Set @z = -x@.
+ */
+
+void f25519_neg(f25519 *z, const f25519 *x)
+{
+#if F25519_IMPL == 26
+  z->P[0] = -x->P[0]; z->P[1] = -x->P[1];
+  z->P[2] = -x->P[2]; z->P[3] = -x->P[3];
+  z->P[4] = -x->P[4]; z->P[5] = -x->P[5];
+  z->P[6] = -x->P[6]; z->P[7] = -x->P[7];
+  z->P[8] = -x->P[8]; z->P[9] = -x->P[9];
+#elif F25519_IMPL == 10
+  unsigned i;
+  for (i = 0; i < NPIECE; i++) z->P[i] = -x->P[i];
+#endif
+}
+
 /*----- Constant-time utilities -------------------------------------------*/
 
+/* --- @f25519_pick2@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@ or @y@)
+ *             @const f25519 *x, *y@ = two operands
+ *             @uint32 m@ = a mask
+ *
+ * Returns:    ---
+ *
+ * Use:                If @m@ is zero, set @z = y@; if @m@ is all-bits-set, then set
+ *             @z = x@.  If @m@ has some other value, then scramble @z@ in
+ *             an unhelpful way.
+ */
+
+void f25519_pick2(f25519 *z, const f25519 *x, const f25519 *y, uint32 m)
+{
+  mask32 mm = FIX_MASK32(m);
+
+#if F25519_IMPL == 26
+  z->P[0] = PICK2(x->P[0], y->P[0], mm);
+  z->P[1] = PICK2(x->P[1], y->P[1], mm);
+  z->P[2] = PICK2(x->P[2], y->P[2], mm);
+  z->P[3] = PICK2(x->P[3], y->P[3], mm);
+  z->P[4] = PICK2(x->P[4], y->P[4], mm);
+  z->P[5] = PICK2(x->P[5], y->P[5], mm);
+  z->P[6] = PICK2(x->P[6], y->P[6], mm);
+  z->P[7] = PICK2(x->P[7], y->P[7], mm);
+  z->P[8] = PICK2(x->P[8], y->P[8], mm);
+  z->P[9] = PICK2(x->P[9], y->P[9], mm);
+#elif F25519_IMPL == 10
+  unsigned i;
+  for (i = 0; i < NPIECE; i++) z->P[i] = PICK2(x->P[i], y->P[i], mm);
+#endif
+}
+
+/* --- @f25519_pickn@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result
+ *             @const f25519 *v@ = a table of entries
+ *             @size_t n@ = the number of entries in @v@
+ *             @size_t i@ = an index
+ *
+ * Returns:    ---
+ *
+ * Use:                If @0 <= i < n < 32@ then set @z = v[i]@.  If @n >= 32@ then
+ *             do something unhelpful; otherwise, if @i >= n@ then set @z@
+ *             to zero.
+ */
+
+void f25519_pickn(f25519 *z, const f25519 *v, size_t n, size_t i)
+{
+  uint32 b = (uint32)1 << (31 - i);
+  mask32 m;
+
+#if F25519_IMPL == 26
+  z->P[0] = z->P[1] = z->P[2] = z->P[3] = z->P[4] =
+    z->P[5] = z->P[6] = z->P[7] = z->P[8] = z->P[9] = 0;
+  while (n--) {
+    m = SIGN(b);
+    CONDPICK(z->P[0], v->P[0], m);
+    CONDPICK(z->P[1], v->P[1], m);
+    CONDPICK(z->P[2], v->P[2], m);
+    CONDPICK(z->P[3], v->P[3], m);
+    CONDPICK(z->P[4], v->P[4], m);
+    CONDPICK(z->P[5], v->P[5], m);
+    CONDPICK(z->P[6], v->P[6], m);
+    CONDPICK(z->P[7], v->P[7], m);
+    CONDPICK(z->P[8], v->P[8], m);
+    CONDPICK(z->P[9], v->P[9], m);
+    v++; b <<= 1;
+  }
+#elif F25519_IMPL == 10
+  unsigned j;
+
+  for (j = 0; j < NPIECE; j++) z->P[j] = 0;
+  while (n--) {
+    m = SIGN(b);
+    for (j = 0; j < NPIECE; j++) CONDPICK(z->P[j], v->P[j], m);
+    v++; b <<= 1;
+  }
+#endif
+}
+
 /* --- @f25519_condswap@ --- *
  *
  * Arguments:  @f25519 *x, *y@ = two operands
@@ -533,6 +640,49 @@ void f25519_condswap(f25519 *x, f25519 *y, uint32 m)
 #endif
 }
 
+/* --- @f25519_condneg@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@)
+ *             @const f25519 *x@ = an operand
+ *             @uint32 m@ = a mask
+ *
+ * Returns:    ---
+ *
+ * Use:                If @m@ is zero, set @z = x@; if @m@ is all-bits-set, then set
+ *             @z = -x@.  If @m@ has some other value then scramble @z@ in
+ *             an unhelpful way.
+ */
+
+void f25519_condneg(f25519 *z, const f25519 *x, uint32 m)
+{
+#ifdef NEG_TWOC
+  mask32 m_xor = FIX_MASK32(m);
+  piece m_add = m&1;
+# define CONDNEG(x) (((x) ^ m_xor) + m_add)
+#else
+  int s = PICK2(-1, +1, m);
+# define CONDNEG(x) (s*(x))
+#endif
+
+#if F25519_IMPL == 26
+  z->P[0] = CONDNEG(x->P[0]);
+  z->P[1] = CONDNEG(x->P[1]);
+  z->P[2] = CONDNEG(x->P[2]);
+  z->P[3] = CONDNEG(x->P[3]);
+  z->P[4] = CONDNEG(x->P[4]);
+  z->P[5] = CONDNEG(x->P[5]);
+  z->P[6] = CONDNEG(x->P[6]);
+  z->P[7] = CONDNEG(x->P[7]);
+  z->P[8] = CONDNEG(x->P[8]);
+  z->P[9] = CONDNEG(x->P[9]);
+#elif F25519_IMPL == 10
+  unsigned i;
+  for (i = 0; i < NPIECE; i++) z->P[i] = CONDNEG(x->P[i]);
+#endif
+
+#undef CONDNEG
+}
+
 /*----- Multiplication ----------------------------------------------------*/
 
 #if F25519_IMPL == 26
@@ -913,11 +1063,119 @@ void f25519_inv(f25519 *z, const f25519 *x)
 #undef SQRN
 }
 
+/* --- @f25519_quosqrt@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@ or @y@)
+ *             @const f25519 *x, *y@ = two operands
+ *
+ * Returns:    Zero if successful, @-1@ if %$x/y$% is not a square.
+ *
+ * Use:                Stores in @z@ the one of the square roots %$\pm\sqrt{x/y}$%.
+ *             If %$x = y = 0% then the result is zero; if %$y = 0$% but %$x
+ *             \ne 0$% then the operation fails.  If you wanted a specific
+ *             square root then you'll have to pick it yourself.
+ */
+
+static const piece sqrtm1_pieces[NPIECE] = {
+#if F25519_IMPL == 26
+  -32595792,  -7943725,   9377950,   3500415,  12389472,
+    -272473, -25146209,  -2005654,    326686,  11406482
+#elif F25519_IMPL == 10
+   176,  -88,  161,  157, -485, -196, -231, -220, -416,
+  -169, -255,   50,  189,  -89, -266,  -32,  202, -511,
+   423,  357,  248, -249,   80,  288,   50,  174
+#endif
+};
+#define SQRTM1 ((const f25519 *)sqrtm1_pieces)
+
+int f25519_quosqrt(f25519 *z, const f25519 *x, const f25519 *y)
+{
+  f25519 t, u, w, beta, xy3, t2p50m1;
+  octet xb[32], b0[32], b1[32];
+  int32 rc = -1;
+  mask32 m;
+  unsigned i;
+
+#define SQRN(z, x, n) do {                                             \
+  f25519_sqr((z), (x));                                                        \
+  for (i = 1; i < (n); i++) f25519_sqr((z), (z));                      \
+} while (0)
+
+  /* This is a bit tricky; the algorithm is from Bernstein, Duif, Lange,
+   * Schwabe, and Yang, `High-speed high-security signatures', 2011-09-26,
+   * https://ed25519.cr.yp.to/ed25519-20110926.pdf.
+   *
+   * First of all, a complicated exponentation.  The addition chain here is
+   * mine.  We start with some preliminary values.
+   */                                  /* step | value */
+  SQRN(&u, y, 1);                      /*    1 | 0, 2 */
+  f25519_mul(&t, &u, y);               /*    2 | 0, 3 */
+  f25519_mul(&xy3, &t, x);             /*    3 | 1, 3 */
+  SQRN(&u, &u, 1);                     /*    4 | 0, 4 */
+  f25519_mul(&w, &u, &xy3);            /*    5 | 1, 7 */
+
+  /* And now we calculate w^((p - 5)/8) = w^(252 - 3). */
+  SQRN(&u, &w, 1);                     /*    6 | 2 */
+  f25519_mul(&t, &w, &u);              /*    7 | 3 */
+  SQRN(&u, &t, 1);                     /*    8 | 6 */
+  f25519_mul(&t, &u, &w);              /*    9 | 7 */
+  SQRN(&u, &t, 3);                     /*   12 | 56 */
+  f25519_mul(&t, &t, &u);              /*   13 | 63 = 2^6 - 1 */
+  SQRN(&u, &t, 6);                     /*   19 | 2^12 - 2^6 */
+  f25519_mul(&t, &t, &u);              /*   20 | 2^12 - 1 */
+  SQRN(&u, &t, 12);                    /*   32 | 2^24 - 2^12 */
+  f25519_mul(&t, &t, &u);              /*   33 | 2^24 - 1 */
+  SQRN(&u, &t, 1);                     /*   34 | 2^25 - 2 */
+  f25519_mul(&t, &u, &w);              /*   35 | 2^25 - 1 */
+  SQRN(&u, &t, 25);                    /*   60 | 2^50 - 2^25 */
+  f25519_mul(&t2p50m1, &t, &u);                /*   61 | 2^50 - 1 */
+  SQRN(&u, &t2p50m1, 50);              /*  111 | 2^100 - 2^50 */
+  f25519_mul(&t, &t2p50m1, &u);                /*  112 | 2^100 - 1 */
+  SQRN(&u, &t, 100);                   /*  212 | 2^200 - 2^100 */
+  f25519_mul(&t, &t, &u);              /*  213 | 2^200 - 1 */
+  SQRN(&u, &t, 50);                    /*  263 | 2^250 - 2^50 */
+  f25519_mul(&t, &t2p50m1, &u);                /*  264 | 2^250 - 1 */
+  SQRN(&u, &t, 2);                     /*  266 | 2^252 - 4 */
+  f25519_mul(&t, &u, &w);              /*  267 | 2^252 - 3 */
+
+  /* And finally... */
+  f25519_mul(&beta, &t, &xy3);         /*  268 | ... */
+
+  /* Now we have beta = (x y^3) (x y^7)^((p - 5)/8) = (x/y)^((p + 3)/8), and
+   * we're ready to finish the computation.  Suppose that alpha^2 = u/w.
+   * Then beta^4 = (x/y)^((p + 3)/2) = alpha^(p + 3) = alpha^4 = (x/y)^2, so
+   * we have beta^2 = ±x/y.  If y beta^2 = x then beta is the one we wanted;
+   * if -y beta^2 = x, then we want beta sqrt(-1), which we already know.  Of
+   * course, it might not match either, in which case we fail.
+   *
+   * The easiest way to compare is to encode.  This isn't as wasteful as it
+   * sounds: the hard part is normalizing the representations, which we have
+   * to do anyway.
+   */
+  f25519_sqr(&t, &beta);
+  f25519_mul(&t, &t, y);
+  f25519_neg(&u, &t);
+  f25519_store(xb, x);
+  f25519_store(b0, &t);
+  f25519_store(b1, &u);
+  f25519_mul(&u, &beta, SQRTM1);
+
+  m = -ct_memeq(b0, xb, 32);
+  rc = PICK2(0, rc, m);
+  f25519_pick2(z, &beta, &u, m);
+  m = -ct_memeq(b1, xb, 32);
+  rc = PICK2(0, rc, m);
+
+  /* And we're done. */
+  return (rc);
+}
+
 /*----- Test rig ----------------------------------------------------------*/
 
 #ifdef TEST_RIG
 
 #include <mLib/report.h>
+#include <mLib/str.h>
 #include <mLib/testrig.h>
 
 static void fixdstr(dstr *d)
@@ -982,6 +1240,7 @@ static const test_type
     return (ok);                                                       \
   }
 
+TEST_UNOP(neg)
 TEST_UNOP(sqr)
 TEST_UNOP(inv)
 
@@ -1031,6 +1290,79 @@ static int vrf_mulc(dstr dv[])
   return (ok);
 }
 
+static int vrf_condneg(dstr dv[])
+{
+  f25519 *x = (f25519 *)dv[0].buf;
+  uint32 m = *(uint32 *)dv[1].buf;
+  f25519 z;
+  int ok = 1;
+
+  f25519_condneg(&z, x, m);
+  if (!eq(&z, &dv[2])) {
+    ok = 0;
+    fprintf(stderr, "failed!\n");
+    fdump(stderr, "x", x->P);
+    fprintf(stderr, "m = 0x%08lx\n", (unsigned long)m);
+    fdump(stderr, "calc z", z.P);
+    f25519_load(&z, (const octet *)dv[1].buf);
+    fdump(stderr, "want z", z.P);
+  }
+
+  return (ok);
+}
+
+static int vrf_pick2(dstr dv[])
+{
+  f25519 *x = (f25519 *)dv[0].buf, *y = (f25519 *)dv[1].buf;
+  uint32 m = *(uint32 *)dv[2].buf;
+  f25519 z;
+  int ok = 1;
+
+  f25519_pick2(&z, x, y, m);
+  if (!eq(&z, &dv[3])) {
+    ok = 0;
+    fprintf(stderr, "failed!\n");
+    fdump(stderr, "x", x->P);
+    fdump(stderr, "y", y->P);
+    fprintf(stderr, "m = 0x%08lx\n", (unsigned long)m);
+    fdump(stderr, "calc z", z.P);
+    f25519_load(&z, (const octet *)dv[3].buf);
+    fdump(stderr, "want z", z.P);
+  }
+
+  return (ok);
+}
+
+static int vrf_pickn(dstr dv[])
+{
+  dstr d = DSTR_INIT;
+  f25519 v[32], z;
+  size_t i = *(uint32 *)dv[1].buf, j, n;
+  const char *p;
+  char *q;
+  int ok = 1;
+
+  for (q = dv[0].buf, n = 0; (p = str_qword(&q, 0)) != 0; n++)
+    { cvt_f25519(p, &d); v[n] = *(f25519 *)d.buf; }
+
+  f25519_pickn(&z, v, n, i);
+  if (!eq(&z, &dv[2])) {
+    ok = 0;
+    fprintf(stderr, "failed!\n");
+    for (j = 0; j < n; j++) {
+      fprintf(stderr, "v[%2u]", (unsigned)j);
+      fdump(stderr, "", v[j].P);
+    }
+    fprintf(stderr, "i = %u\n", (unsigned)i);
+    fdump(stderr, "calc z", z.P);
+    f25519_load(&z, (const octet *)dv[2].buf);
+    fdump(stderr, "want z", z.P);
+  }
+
+  dstr_destroy(&d);
+  return (ok);
+}
+
 static int vrf_condswap(dstr dv[])
 {
   f25519 *x = (f25519 *)dv[0].buf, *y = (f25519 *)dv[1].buf;
@@ -1056,6 +1388,35 @@ static int vrf_condswap(dstr dv[])
   return (ok);
 }
 
+static int vrf_quosqrt(dstr dv[])
+{
+  f25519 *x = (f25519 *)dv[0].buf, *y = (f25519 *)dv[1].buf;
+  f25519 z, zz;
+  int rc;
+  int ok = 1;
+
+  if (dv[2].len) { fixdstr(&dv[2]); fixdstr(&dv[3]); }
+  rc = f25519_quosqrt(&z, x, y);
+  if (!dv[2].len ? !rc : (rc || (!eq(&z, &dv[2]) && !eq(&z, &dv[3])))) {
+    ok = 0;
+    fprintf(stderr, "failed!\n");
+    fdump(stderr, "x", x->P);
+    fdump(stderr, "y", y->P);
+    if (rc) fprintf(stderr, "calc: FAIL\n");
+    else fdump(stderr, "calc", z.P);
+    if (!dv[2].len)
+      fprintf(stderr, "exp: FAIL\n");
+    else {
+      f25519_load(&zz, (const octet *)dv[2].buf);
+      fdump(stderr, "z", zz.P);
+      f25519_load(&zz, (const octet *)dv[3].buf);
+      fdump(stderr, "z'", zz.P);
+    }
+  }
+
+  return (ok);
+}
+
 static int vrf_sub_mulc_add_sub_mul(dstr dv[])
 {
   f25519 *u = (f25519 *)dv[0].buf, *v = (f25519 *)dv[1].buf,
@@ -1093,13 +1454,22 @@ static int vrf_sub_mulc_add_sub_mul(dstr dv[])
 static test_chunk tests[] = {
   { "add", vrf_add, { &type_f25519, &type_f25519, &type_f25519_ref } },
   { "sub", vrf_sub, { &type_f25519, &type_f25519, &type_f25519_ref } },
+  { "neg", vrf_neg, { &type_f25519, &type_f25519_ref } },
+  { "condneg", vrf_condneg,
+    { &type_f25519, &type_uint32, &type_f25519_ref } },
   { "mul", vrf_mul, { &type_f25519, &type_f25519, &type_f25519_ref } },
   { "mulconst", vrf_mulc, { &type_f25519, &type_long, &type_f25519_ref } },
+  { "pick2", vrf_pick2,
+    { &type_f25519, &type_f25519, &type_uint32, &type_f25519_ref } },
+  { "pickn", vrf_pickn,
+    { &type_string, &type_uint32, &type_f25519_ref } },
   { "condswap", vrf_condswap,
     { &type_f25519, &type_f25519, &type_uint32,
       &type_f25519_ref, &type_f25519_ref } },
   { "sqr", vrf_sqr, { &type_f25519, &type_f25519_ref } },
   { "inv", vrf_inv, { &type_f25519, &type_f25519_ref } },
+  { "quosqrt", vrf_quosqrt,
+    { &type_f25519, &type_f25519, &type_hex, &type_hex } },
   { "sub-mulc-add-sub-mul", vrf_sub_mulc_add_sub_mul,
     { &type_f25519, &type_f25519, &type_long, &type_f25519,
       &type_f25519, &type_f25519, &type_f25519_ref } },

diff --git a/math/f25519.h b/math/f25519.h
index a70ca2d..fc75546 100644 (file)
--- a/math/f25519.h
+++ b/math/f25519.h
@@ -108,6 +108,39 @@ extern void f25519_load(f25519 */*z*/, const octet /*xv*/[32]);
 
 extern void f25519_store(octet /*zv*/[32], const f25519 */*x*/);
 
+/* --- @f25519_pick2@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@ or @y@)
+ *             @const f25519 *x, *y@ = two operands
+ *             @uint32 m@ = a mask
+ *
+ * Returns:    ---
+ *
+ * Use:                If @m@ is zero, set @z = y@; if @m@ is all-bits-set, then set
+ *             @z = x@.  If @m@ has some other value, then scramble @z@ in
+ *             an unhelpful way.
+ */
+
+extern void f25519_pick2(f25519 */*z*/, const f25519 */*x*/,
+                        const f25519 */*y*/, uint32 /*m*/);
+
+/* --- @f25519_pickn@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result
+ *             @const f25519 *v@ = a table of entries
+ *             @size_t n@ = the number of entries in @v@
+ *             @size_t i@ = an index
+ *
+ * Returns:    ---
+ *
+ * Use:                If @0 <= i < n < 32@ then set @z = v[i]@.  If @n >= 32@ then
+ *             do something unhelpful; otherwise, if @i >= n@ then set @z@
+ *             to zero.
+ */
+
+extern void f25519_pickn(f25519 */*z*/, const f25519 */*v*/, size_t /*n*/,
+                        size_t /*i*/);
+
 /* --- @f25519_condswap@ --- *
  *
  * Arguments:  @f25519 *x, *y@ = two operands
@@ -148,6 +181,33 @@ extern void f25519_add(f25519 */*z*/,
 extern void f25519_sub(f25519 */*z*/,
                       const f25519 */*x*/, const f25519 */*y*/);
 
+/* --- @f25519_neg@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@)
+ *             @const f25519 *x@ = an operand
+ *
+ * Returns:    ---
+ *
+ * Use:                Set @z = -x@.
+ */
+
+extern void f25519_neg(f25519 */*z*/, const f25519 */*x*/);
+
+/* --- @f25519_condneg@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@)
+ *             @const f25519 *x@ = an operand
+ *             @uint32 m@ = a mask
+ *
+ * Returns:    ---
+ *
+ * Use:                If @m@ is zero, set @z = x@; if @m@ is all-bits-set, then set
+ *             @z = -x@.  If @m@ has some other value then scramble @z@ in
+ *             an unhelpful way.
+ */
+
+extern void f25519_condneg(f25519 */*z*/, const f25519 */*x*/, uint32 /*m*/);
+
 /* --- @f25519_mulconst@ --- *
  *
  * Arguments:  @f25519 *z@ = where to put the result (may alias @x@)
@@ -200,6 +260,22 @@ extern void f25519_sqr(f25519 */*z*/, const f25519 */*x*/);
 
 extern void f25519_inv(f25519 */*z*/, const f25519 */*x*/);
 
+/* --- @f25519_quosqrt@ --- *
+ *
+ * Arguments:  @f25519 *z@ = where to put the result (may alias @x@ or @y@)
+ *             @const f25519 *x, *y@ = two operands
+ *
+ * Returns:    Zero if successful, @-1@ if %$x/y$% is not a square.
+ *
+ * Use:                Stores in @z@ the one of the square roots %$\pm\sqrt{x/y}$%.
+ *             If %$x = y = 0% then the result is zero; if %$y = 0$% but %$x
+ *             \ne 0$% then the operation fails.  If you wanted a specific
+ *             square root then you'll have to pick it yourself.
+ */
+
+extern int f25519_quosqrt(f25519 */*z*/,
+                         const f25519 */*x*/, const f25519 */*y*/);
+
 /*----- That's all, folks -------------------------------------------------*/
 
 #ifdef __cplusplus

diff --git a/math/t/f25519 b/math/t/f25519
index a2264bc..96d4ac7 100644 (file)
--- a/math/t/f25519
+++ b/math/t/f25519
@@ -138,6 +138,574 @@ sub {
     c5f42c73614ca5377a0ea473c6bc4ac35e696855b9685b10dd64ad2ae42cf467;
 }
 
+neg {
+  0000000000000000000000000000000000000000000000000000000000000000
+    0000000000000000000000000000000000000000000000000000000000000000;
+  23d767107e23d5ce14189cce939c4b5334d6736da3da40a715236b9d8319efc1
+    b72898ef81dc2a31ebe763316c63b4accb298c925c25bf58eadc94627ce6103e;
+  9bb944cfb58b186cc551e0a0eca74528c7618ff47485bf6a723f43d990f69f6e
+    5246bb304a74e7933aae1f5f1358bad7389e700b8b7a40958dc0bc266f096011;
+  bff36d2aa923d5a9af5398e2cfcba4acdf3c3181a8ff00b8a1099cd97a4e8542
+    2e0c92d556dc2a5650ac671d30345b5320c3ce7e5700ff475ef6632685b17a3d;
+  1b65a51746eabb7c0d8d9844dda03bde7128407e94661db2d5fd9c0f3790d120
+    d29a5ae8b9154483f27267bb225fc4218ed7bf816b99e24d2a0263f0c86f2e5f;
+  88f4cf29a610c4465f63a272fde2f19a4874a70a0829885014379b637ab0e82d
+    650b30d659ef3bb9a09c5d8d021d0e65b78b58f5f7d677afebc8649c854f1752;
+  94ca4d567efcf088e6bf1cb3698f6b8bf2164db4f523e28781aebfcbb501ec63
+    5935b2a981030f771940e34c967094740de9b24b0adc1d787e5140344afe131c;
+  3f8d7ae4f1698921524e49ccb2ce4459e4c048f76f04c5e60179f5417d2d52db
+    9b72851b0e9676deadb1b6334d31bba61b3fb70890fb3a19fe860abe82d2ad24;
+  1eaa0c45af0d8f85d865cc66ff3d0dc3355f1ac36821cdd95a6b9232a27f9044
+    cf55f3ba50f2707a279a339900c2f23ccaa0e53c97de3226a5946dcd5d806f3b;
+  33e142c78ee87a7980ade6c796e7ff949cee6d3af0415bf5b6901f84c2db910a
+    ba1ebd38711785867f5219386918006b631192c50fbea40a496fe07b3d246e75;
+  24a0c185c47787caf1a666a62002a503f2a3e591e5f2946e148a47b9b114a884
+    b65f3e7a3b8878350e599959dffd5afc0d5c1a6e1a0d6b91eb75b8464eeb577b;
+  a8bd0c1c3f219a97de87b22e8cb3eb5daea33b5646589b6925ec4ec83ca37455
+    4542f3e3c0de656821784dd1734c14a2515cc4a9b9a76496da13b137c35c8b2a;
+  1a340d2679ca205f6b198cff4bffadcde1afeeed124ef0c574655dbe8732b681
+    c0cbf2d98635dfa094e67300b40052321e501112edb10f3a8b9aa24178cd497e;
+  da43c139a1f92ba1b5fc996befe5218368eac3c46b42e98a9cca8b8f6f1540f5
+    00bc3ec65e06d45e4a036694101ade7c97153c3b94bd16756335747090eabf0a;
+  81aad864a31e5f4afa32c29eb97f22c103dfe5b1323db05fc9b1545312aa6c0d
+    6c55279b5ce1a0b505cd3d614680dd3efc201a4ecdc24fa0364eabaced559372;
+  28231ad38d214f1421df7005eddb4f4c12e522b10d1cbcd10ee26dfcc222a62c
+    c5dce52c72deb0ebde208ffa1224b0b3ed1add4ef2e3432ef11d92033ddd5953;
+  c1facefef35c1ed00db767ed0281ebfad1f3c915c6649f5e1c26a6f3f9478b43
+    2c0531010ca3e12ff2489812fd7e14052e0c36ea399b60a1e3d9590c06b8743c;
+  c2e4046e7200386ca2afea8ecc9c98c105fbf6e31b598e21e482796a69956040
+    2b1bfb918dffc7935d5015713363673efa04091ce4a671de1b7d8695966a9f3f;
+  a42fedea4eac90580a0bbcb0491a7e8cc82de7a99aa74ed35f705c536afa0236
+    49d01215b1536fa7f5f4434fb6e5817337d218566558b12ca08fa3ac9505fd49;
+  d1ab8c50d54279ceac870d0ce4a2af56bf8c03e87482dcb7775183a4908ac739
+    1c5473af2abd86315378f2f31b5d50a94073fc178b7d234888ae7c5b6f753846;
+  1ffd85fa5ead53ff509756fc28051ef65eca040303b65f7b5b7e1d1a8508e030
+    ce027a05a152ac00af68a903d7fae109a135fbfcfc49a084a481e2e57af71f4f;
+}
+
+condneg {
+  5330763b29dff20501a1d6c64025c36279083473721f5cacf89168189ff9810d
+    0x00000000
+    5330763b29dff20501a1d6c64025c36279083473721f5cacf89168189ff9810d;
+  9d9c36e2126d911a503e1cc1a8489ee74949ae2a8408dc7d72ed0d75e4350545
+    0x00000000
+    9d9c36e2126d911a503e1cc1a8489ee74949ae2a8408dc7d72ed0d75e4350545;
+  47da10abec2cb54c5890e5945999deb1d89ffd268bbbe2eafc86f1acc8bf5f7e
+    0x00000000
+    47da10abec2cb54c5890e5945999deb1d89ffd268bbbe2eafc86f1acc8bf5f7e;
+  3e6ec07de86be6ffab2dfa1deb9ed67844645be92bdbb22b7ba91379babcdfed
+    0x00000000
+    516ec07de86be6ffab2dfa1deb9ed67844645be92bdbb22b7ba91379babcdf6d;
+  5f5c0730649586b5c0b60a14d3b669b3649eb6725d71d834e78ff2aa0e5450e5
+    0xffffffff
+    7ba3f8cf9b6a794a3f49f5eb2c49964c9b61498da28e27cb18700d55f1abaf1a;
+  c357befcc6836d89387915e368e5e6162252b433eb58d94eb3cc4b783e98c226
+    0xffffffff
+    2aa84103397c9276c786ea1c971a19e9ddad4bcc14a726b14c33b487c1673d59;
+  713ad0f656a8fcd75fdee2c4ac248ee7ad09a5f357c565daa94ae46d8590d2c8
+    0x00000000
+    843ad0f656a8fcd75fdee2c4ac248ee7ad09a5f357c565daa94ae46d8590d248;
+  909d669185e98b4a88a6531b830193b23035d64665929e34e86d53c4a9eef30a
+    0xffffffff
+    5d62996e7a1674b57759ace47cfe6c4dcfca29b99a6d61cb1792ac3b56110c75;
+  8f23ec139f93258e6d57fa278339f1cb5da193c5d1ad7183fb2b151111262285
+    0x00000000
+    a223ec139f93258e6d57fa278339f1cb5da193c5d1ad7183fb2b151111262205;
+  a9a5480c72157f389be80ae7ad63502434c380ccd1cef813dc9bd2e9a85e2f22
+    0xffffffff
+    445ab7f38dea80c76417f518529cafdbcb3c7f332e3107ec23642d1657a1d05d;
+  316f98b6697e7daa8775d3aa91dee8fbbae4e935a2f62cd2975e2d552f0c9846
+    0xffffffff
+    bc90674996818255788a2c556e211704451b16ca5d09d32d68a1d2aad0f36739;
+  70128d6dd5fb42f287fba3533c71cb5dc2361b6d91c3d9626c58849e27f7d349
+    0xffffffff
+    7ded72922a04bd0d78045cacc38e34a23dc9e4926e3c269d93a77b61d8082c36;
+  66a6f3dc6274e4122dc401ef23529175d71d96b660a52cdcd64556073b5430b2
+    0x00000000
+    79a6f3dc6274e4122dc401ef23529175d71d96b660a52cdcd64556073b543032;
+  3909505812b228e6ca5cc6c0b17824ef765923eded6105e6eb0f176781624c5a
+    0xffffffff
+    b4f6afa7ed4dd71935a3393f4e87db1089a6dc12129efa1914f0e8987e9db325;
+  b7febd7d63efae3bcc60c1c344f2f6166b272eed785a9e541d3ff4f12e82a5f3
+    0xffffffff
+    230142829c1051c4339f3e3cbb0d09e994d8d11287a561abe2c00b0ed17d5a0c;
+  d1cacc1db40de13351224046975319d7546ae9e88e1909c2a8f46792a140d279
+    0xffffffff
+    1c3533e24bf21eccaeddbfb968ace628ab95161771e6f63d570b986d5ebf2d06;
+  4c449a50fc1e145be1463e4c171b3c51c9683c41c45005d8aeca607911c9b3be
+    0xffffffff
+    8ebb65af03e1eba41eb9c1b3e8e4c3ae3697c3be3baffa2751359f86ee364c41;
+  c929c50eedbad6ceacdefb00bd58a32820c874c906741e9d93cd0f668819edcc
+    0x00000000
+    dc29c50eedbad6ceacdefb00bd58a32820c874c906741e9d93cd0f668819ed4c;
+  1c57449dcfc7e8f9fab77d226d4b50d7dee06c29d08d3d4f4ae7c8ad238a0a82
+    0xffffffff
+    bea8bb6230381706054882dd92b4af28211f93d62f72c2b0b5183752dc75f57d;
+  396a2ddc48f158e73c95dc289da3f0d3b2128875e20c401cb50fd6cc7a28dd18
+    0xffffffff
+    b495d223b70ea718c36a23d7625c0f2c4ded778a1df3bfe34af0293385d72267;
+}
+
+pick2 {
+  e6f52222f35081896f3d9ecc0ffb27fa3e75c8ad1c98e161878d2c3cffd72c78
+    a24cd71f7acb653466b7d67bb41efb5a29503d2627d2ce28fe19680ccd939be5
+    0x00000000
+    b54cd71f7acb653466b7d67bb41efb5a29503d2627d2ce28fe19680ccd939b65;
+  4e51fe2dac96a664d0675962116b7af4e605194a1c9fb774c621a3107994c9ed
+    508934be10ce5e11e6940d56e84b148e20f48369e748536846763c80bab9af49
+    0x00000000
+    508934be10ce5e11e6940d56e84b148e20f48369e748536846763c80bab9af49;
+  530175217081c3fb3ecd17702ad334ad48f05affd5ab3754ef10be5b0eb5375d
+    8aebc7e01e2bb2829f21311462175948d85cd3e65d676eec893e3df13f639d07
+    0xffffffff
+    530175217081c3fb3ecd17702ad334ad48f05affd5ab3754ef10be5b0eb5375d;
+  0e53c5141d72c8c81d80b1a1283b0267b278f98e28ce08ccac7b010022e5adae
+    2215cc15e950d6abfffa26113f269628f50f9ac37ad3260ae9189958d75080b6
+    0xffffffff
+    2153c5141d72c8c81d80b1a1283b0267b278f98e28ce08ccac7b010022e5ad2e;
+  3dc16434679d30686d5023fda4cc574563841caf1d588e965fe1ec1c4ba54398
+    4ca50330751d33ebba981277926a3fb801d216474cb183f90947680f5ea383a2
+    0xffffffff
+    50c16434679d30686d5023fda4cc574563841caf1d588e965fe1ec1c4ba54318;
+  09e68cb66b5ae2f3160a71738d1e9a042b9b76335eddc4b9466d0c6b8100eeb6
+    270eb833ae635bed17df9218a53a91b7afeb74f0df3bfffb8334c04773cf716d
+    0xffffffff
+    1ce68cb66b5ae2f3160a71738d1e9a042b9b76335eddc4b9466d0c6b8100ee36;
+  831b8a99e3b44bf21cdd4f3c06da7c16a95e98f3dc42cf2ac282edec67d9b2ca
+    482840e31c7620de6d290d747afc63ca199c60169f8eb62d28ca1142c5336990
+    0xffffffff
+    961b8a99e3b44bf21cdd4f3c06da7c16a95e98f3dc42cf2ac282edec67d9b24a;
+  a022ace6772d82d30832328c7cbfedb622b710d1fe9313a77dc4cc5ca577a7bb
+    39c86c57bf581c16d8c03b4ef0fe813815b5da1281f03bb3f2cdb0ddf19868d0
+    0xffffffff
+    b322ace6772d82d30832328c7cbfedb622b710d1fe9313a77dc4cc5ca577a73b;
+  719d3f13c38b915873bcb14308bfd9bb6f4a6cfd249a745bceb55787ce480caa
+    c72de6e206ed24555d091763644d4405f2ee5dbd846a036d6a21442a6c40e0c6
+    0x00000000
+    da2de6e206ed24555d091763644d4405f2ee5dbd846a036d6a21442a6c40e046;
+  07cdd3cd677a3c1783bcf7855bf1dbb453809b66c66c7bbbb67690cea33ca581
+    c9d889281ac117390875739e4b62df6dc3cca6c65439c46bb907c81d3a961fa3
+    0x00000000
+    dcd889281ac117390875739e4b62df6dc3cca6c65439c46bb907c81d3a961f23;
+  a69a728035cc69d5d3f96dd4a8081864333e53e434820dd569deb9e58393d4b7
+    3f4ef71dfa1eccd817d3192dbe2e08466e4a66b4d836b0892b3636dc523098ed
+    0x00000000
+    524ef71dfa1eccd817d3192dbe2e08466e4a66b4d836b0892b3636dc5230986d;
+  d249414415ac4960e934d29e08c75ff1b18431a6e18f7404e638293d3d8e81d5
+    33cd02e07762f74976834d1b6dd3b8eb7e2ad7a5d04ba90bbe747476071f10cb
+    0x00000000
+    46cd02e07762f74976834d1b6dd3b8eb7e2ad7a5d04ba90bbe747476071f104b;
+  efb782aba4dca351a5c9279b370073840b977b2458c6c84c9c9046dc92cc5507
+    6d9f50eb56b84989aab77c54987f05c715b74185417863f2c275635d2d6f2eeb
+    0x00000000
+    809f50eb56b84989aab77c54987f05c715b74185417863f2c275635d2d6f2e6b;
+  10c4381ed467e27d756ff7a260a6ffd282ad757b10c9956c518a43117699ee91
+    9b9a70c67be3296ef9d65fdd8014c4b263c28fd31f3299f4461c688c469ff704
+    0x00000000
+    9b9a70c67be3296ef9d65fdd8014c4b263c28fd31f3299f4461c688c469ff704;
+  5a30428bee407ee673ec7d2cb4854efd80b9761df5dec906463f888f60be7152
+    fc2e139be53203eb73041e9335253534c420208164682c2e02f31f084f5582f0
+    0xffffffff
+    5a30428bee407ee673ec7d2cb4854efd80b9761df5dec906463f888f60be7152;
+  43c7cd903c7dd7cdab85c6b5585955163e0da7dd0c5b5882ac620246619af342
+    0eb52162c69425ad75b778c39746014789f7929119d4e122d4b98bf64784fcde
+    0xffffffff
+    43c7cd903c7dd7cdab85c6b5585955163e0da7dd0c5b5882ac620246619af342;
+  f37f3707e4609d389096c1fea551b572a6b4644fd6af2e9e7a0fa93a91ae38e5
+    d10dd4d911346a5952e3123d4f156a7e40807d142c4afb4bc314ac6f9346dfa8
+    0xffffffff
+    06803707e4609d389096c1fea551b572a6b4644fd6af2e9e7a0fa93a91ae3865;
+  a4f4c203cb892691a6d6e9dff8a10ac1a8d9470b13ba24e1bddac05d6d7f9c0e
+    b88145fabdeaa9fa108bb04a4d283ac034b4c8d8ffe1b2174de9a80254762c54
+    0xffffffff
+    a4f4c203cb892691a6d6e9dff8a10ac1a8d9470b13ba24e1bddac05d6d7f9c0e;
+  649d8ce64f623228553de99b823c5f5c5ef37f00e2ddf658fc9bc2405afde715
+    0f24ace92223d2db75e2d82e8a5bc8b0e7981478216b999d2bdde9c72732d58f
+    0xffffffff
+    649d8ce64f623228553de99b823c5f5c5ef37f00e2ddf658fc9bc2405afde715;
+  3f466e24ed4169ca3df624d747f054f97422d5eee3fade2fa3c4eba488694a6c
+    37e3171c9aa56d07ffcde4f1fd0fdcc41e2086ecf93c9e53f3f6a4c3e4db587c
+    0xffffffff
+    3f466e24ed4169ca3df624d747f054f97422d5eee3fade2fa3c4eba488694a6c;
+}
+
+pickn {
+  "91aaaaf3ff9e58f299c0f6d0a4a3851d100423e4b7380d5a32a86cde6cb19562
+   e586b4ab140cd20bfc70aa5ae1c389941a8c631ce033f54793d77c91b5e3d50b
+   911122291921aced748e1346261ce8dc0e50704bf59495c3d7c1a9806ae58b5e
+   dac7c42fc0253029c78310ea1508b2464db2c44689fa7d485fb5863b7c136f15"
+    0
+    91aaaaf3ff9e58f299c0f6d0a4a3851d100423e4b7380d5a32a86cde6cb19562;
+  "e8864778a3aecd6f35f8afa097072e94c4e50680baf91a6036f4f24fb0dcf111
+   5dec44933a517f5a8bf6d858920e1200c74e65132baf0d08ca033e36e15a1c46
+   4fca88e6d122c0a460b5dd502281d80616edd30bede891226b4b3c4b3eb9eea0
+   5fbf4e034d45326d89ffe92bf4738a7120c63ea42568c25acacf4dd7915b9e8f
+   343001277d416dd31dc770232fc47c7d02884fef3fc10eaddf6f8b42fbb00b26"
+    1
+    5dec44933a517f5a8bf6d858920e1200c74e65132baf0d08ca033e36e15a1c46;
+  "f0cfc16fe0cb8910c26f6f46e69954dd34277d171044140c2dc448b6f63e053c
+   d54feccab8d55297eb24f622818aaa2ac5b7fcafee5efe872bb600cbdce85a3a
+   5f1cb6c6b4e8eedb566150a99a7c92228e7f737efa1810b9d40f9a4ea020e56d
+   c762a32a3f3a6f8cd956412eacdaa75ee56b347b952a7c18dd19c0ee2e50b8fc
+   b6e76d1d2cdf04692036f26515ca6b92d57b1bba625f07553d2d4adf89de9611
+   874c9e94d425fe9590aa1cde396ec56531342207a0e3b42ef0ae710bc9b68418
+   872ebc0bbd45d07727887aa8116a5743880093c73b3048c3b46920c04e0f64e2
+   9cde037629d20a4481ba7050546eca2dfd293b0953aa708764531bd8d0fba387
+   e9f7cb8ed4af14ac61722de66406e97ee9a87d9362dfa87e489a9c98f8b891b6
+   6c5bb4410d83505ad34d10409d02fc005a47ef802b5d9130f3b5d385ff78957e
+   ff40983b47e7263665a03e4396421fc34209afaf52d7d69012833b4a228e6c40
+   4588ed141f6401c460ff6ad4888172c9d19f15f214d96bedd59f818d7c03b720
+   99ede977304bc4e8f5edc44463b48fc13c001f5c584f2b100c791ae472fdddba
+   8ba76d6aa98a062e1091ca60e05ecf21208657bf287f20c6cacaaeff41a537ff
+   a18760b118187f5b392637dd5c5f97ccce583b5b84b69f8e37d8caf77c616db0
+   7e921cc5caa3b3884358cb0ffd2d9d160ed54256049fa1540d861dbb6dd1631d
+   aa8102188fbba89c45259c52080b3969c234d070411bc4b91870a8b482eedfbf
+   d98da58b248507edf310beb9fb522dd23d88bc0412ef3b5bd7a13b7a15070647
+   0626183221836da09c9bb5a1dd07df570883af17a9a8fed1c4bc7e8770e348fe
+   16b01a5593b3eaf0902d0ade7e00da7b7a57556c2e7169e8b6ba5df5c5fb02a5
+   e40715b07034e109d79a95a8b031eebc6c59dd0bb77de6cb960fe65a6d1be59e"
+    20
+    f70715b07034e109d79a95a8b031eebc6c59dd0bb77de6cb960fe65a6d1be51e;
+  "e30f85631b4ea4aadb9487c76cbec40ab63101a482e5aa2e3ee329fc21071bf4
+   8bc9fdd41fe1ecf5c2cc2075c72e4ceab370b099ddc672ee16bbd7a7de19dbb4
+   ede086a76fedddb463d9f0fb44b39ac7fb64665061eb96015d4ed39eb33cd772
+   a7cd74dc0c94aa8bfa480a88396b7f293f1ac329e4ce79e04507be4edbf4fef1
+   45f5c114a46bf0b2c8be1ecb8fc7c81e7fef668a2e4e9769f2f2dfecf405af92
+   123d101a02348f81088beeb6fafb7f720b49631736829d2f19e95b8d833684a3
+   ba936ae1b5555b05601c2e59bf9585846ac01b5b7f6fe4bbd45e0653e961deaf
+   51c0c307d99e34a617ead92dd37e1a0f36ebe2e45ef5b3690fd114099d483dc6
+   af94cee7979c057995680c3a5adfe26e7dea759e2640b0b09aff383fa355d289
+   6ddb6908532c513f463473e449747f88d47766460ad316734c2cca87963b3060
+   88192953b60710667d47633be71d87214d2dc8be882ceb6928daf311499d2e83
+   37da1b76c2c16025f0644b6451027c8bc9768379c3aa7ab8410d34d8c8222706
+   1a46c0531cc13f546e001a67721931f4f6bf8eeeadaaab667ee651db0b272509"
+    7
+    64c0c307d99e34a617ead92dd37e1a0f36ebe2e45ef5b3690fd114099d483d46;
+  "9929839bce983fe53c4f8f9d07a462f82e8eebabba2c0daee1378abf585bb53d
+   4e47d3997d6562c7b0347acc96925bd1907bf3a9c57d51b099c4a574d7bf8fc7
+   a0de02656ba18dd1cfdb2938fbb864f9f59001110391ee1818f5c1dfee64f61a
+   9c4153154f5b827bb847edfa04ce754e442f2e96ea001fc27f6d94ea8b06fc00
+   7ba90562980966abd857be3a84c1bffeabbb589415e722e51225f8317e829777
+   ac4657b264ccfad4f5ba3f7a470458101d5c6025c45d00191ddd4bf85ca48705
+   8b11cfc6ceb02c5d4b3e19c19f1ae745fd0cdfd9da1a80e9df1be8f7bb99ace3
+   1202bae1f86d05ed8fca09965bb1cfa3fb696a3f2b7089ee10589394639da2bd
+   143f799fc9ebec77aa444eb5ec95f64029cf61b875a2f94e228323844cb8eff9
+   dcf99568b397db79bd2e8ae49778e1e49865e91525f932a1813d1c395420a43c
+   84fdfee8137558f0b9f2441c375fce466e3212c0d0de3179919fb130e61b711a
+   602454ffaf59610f76863a7456146f866539740d6dae63a3628d408e34db8e76
+   86ae4475d41ea312a97c821ac78b815e459dc6bb4d52c236a39e5e53ff17f5fb
+   0fd56e878b74a2daebc2acc30c31c279f3dab146d748e7aa9b17eda7ac039c8f
+   e559e8bbd51113f84ebbe35ab16bfd46cf610a5c61307b986111ddbee3037f7a
+   bac90f3afdf4f4828368090958aef5e49aa83d25fc5dc15d9b8a354a30961e75
+   253eee8f614306e59a31d9fab5423ea269b67babd54c52243b86b8af1372f3ab
+   69828b787af1831f772a3bb9a410dac8bc47909ac6bddc94a5c600a3167ce780
+   1903e9ca239847045875b0bd4e1575a724d9f729e3cbfc377de17ad29839a121
+   57bc65c0fd8495014f31e3be740967f3fd1884bee743b20b947339923530d63d
+   cf7427ebf6088e6f3385275f993b5c06ee14f738b59d49ecc327521ddced2a4a
+   74c2a4122225e97b646d6a38584626a6ed811506ee7cd00b48ba563b7a776380
+   604f163d7d7f4987c8aaf2e7a946cec1597ebeb59aaeaad0dbd0737527b9350a
+   30e7ae69cd5fb42ec00ca840988a59bf5688aa0b810bb2e9ea24fb5b322891a0
+   68caff542deb61b055bf65127a94d8ab107f5d2496764f97351dbbfbf34928e4
+   c0d307ece7f18150d958bd88bf11912dc818fac7cae06ca9ec3fafd15d452af8
+   731b9ae286f29660fd0814568351bd6da114f3ee8b87c217cfe531746faa8c90"
+    8
+    273f799fc9ebec77aa444eb5ec95f64029cf61b875a2f94e228323844cb8ef79;
+  "85b3448d0292edc0b14cfae9225989a16a61ee8441166d5b97faf876b0ab6c7d
+   88b0f7c78f8390b6cc1de0afda111326dbb41e7603b82033902eb56ea542c2dc
+   daf45d38b24294648a7b203758ff0654d42507e958bbd98c72229aae0a9e5757
+   98b44fbbf6e45c81c2473b626307506881a9fa609c546741b3637b731ff62adb
+   c0779c0f0a35658998ee9cb6b0cb6b7e089b7f288ea171c18bd2664ca5c3fc1d
+   8da42494a2c1e2034d2009fd486cc230085fcc8af171e2bc2cf428bbf9b4bc86
+   6dfb99cec539941c9e7d26e5640641e4ef2c3f1a732f9c85759858a95c346ea1
+   471a369f8d1d3341ac707f1c41e5f0655cae51d8a170037ee349b3c14e01be2d
+   c1b75b02941ae0c2e398a2c8871955c8306f6ab88cdc6d751e11b35605d10829
+   ea508e41e33ca0b03b5d93a54ec359e01a5a00a98a80f7e6d998641a6cb7ef58
+   bb009a72b5d5be344a3ba9509b6e8eafbafdab4b0ec9202c8d29983935c6937a
+   fdce2ff0df8548fd7df3b8a087aa30c819af0eff3b8931e5ddedfdb0f4450919
+   eea3990f7f4045a3b6cdae27e4dc8a8062049ac4423ce46108ab464d866b80f3
+   a18000f37c8c4a30195e71864b14f170a3f5c427f4769c736fbdc18b3fe68887
+   ba9aa19e99a69b34f357f92d95a6c409f1bb331d1d27b693164cd0dbb552c771
+   b5863e0215351b2f9b6f661ab94c833016bdef73a34b100b6db79ea8d4b22ec3
+   983eb31be6cd1cd4cb53e489e4535683e21c00e6c52f685e84bd3cfc98f9ab2b
+   c31c18c6c12feb3be4e51a1671fa6001c1dfadc0ebb35349766d9d07d5a70025
+   6f81695294071c711947499c2c3d96969a70948c29ea9506ff675d25052f0950
+   3b42ffd7fb054072e7fb93bfa63d24511e6c93455cdd5b9be3c8382a3cdbfba4
+   6d7463ce0227e29a2706b8ad6be0d6cefa173c261697520b23edb87a189d31eb
+   f6cea0722a490515f48632f42f167a911ba00fd9883604e52d713210f3d9475c
+   6281bf17cc14876c75e9620d8bb9bfd6e4dceae1ad3cb675769f94623ab3a955
+   2c943465a6d4484c71b2c5ae26e1d738059667093450cff54e6b45f12a7588f4
+   3d9ba6aad36754c5c767a0f288b6dbfcd2f1e21bd14094f4ddfb7c4bb79ef882
+   052e95ca0672218808e36c18e1fdee412a945ad735ea883abd527dfe8343a51d
+   3f8ec0ccd82005e01ffd1fd7413a2a1dce1a177cf53474904cc46abdffd22a22
+   2030168387fa230e7a77eae5f051b4e0f1cbc53a78a5df640479c9fc373b9d78
+   3abd6a4fb5a585bb1b4609cebbbd1035392c7565654331a173092c098e1583a2
+   6bceb64086f3874854b4c89d31d20d8772b2f48be6a5fa1fe572be9927345103"
+    2
+    daf45d38b24294648a7b203758ff0654d42507e958bbd98c72229aae0a9e5757;
+  "8a9e76766b2eeda9b4de923344005a825bd2475bc4d529b033de3510cd405b73
+   5206880a0e1c282a10e03253c787e005bc9a18613b6e238f1eb72c604844a2ab
+   acd4fe99d1df199ca20c743238a2bf9562ea4de7b82061d1a6861d77146bdfb8
+   6dccfdff241fd837508913d7e0b1ca3e7a426be578c2e82612f7d2b2491f08f1
+   76aa8f5fb4b3592ff58785ea27d287fa5f250fb84fc9838fad8d6a2cfc223dad
+   71019d81508491afb6a33d8c99aba13d59c63bb88a2ba1182c144f171ed5a815
+   f6ab8f0b95fcaad29def12e05f348a9a35449c7ef5e2859748e69c517f4f3f65
+   237b33cbba9ebcae93f8a4fd863f62a03651be2e936ddb5a62dd3b6a68734b2a
+   4bbe3113be34a9f7fa26dd96258d1776797b8ea454a2f596ae076bdc0f5d0ff0
+   19ae0acbd7ba59869b51caa13e1041bcffed633235a858f39d0d583575a64123
+   cc5e18fdfedf9a416727f81b24a227c0c0771565fff69fc3e19399a254d8c9c5
+   50765357fa421d9153c1f02adcc98f188d2aac6a39fc8d522c5e81fbb775bdbe
+   10e3e53b7605240cadc28c4d3aeb1afe40b7d1d547f4ad60c8d03006b42fb499
+   aec6bfd729a6e2898890c9ee15338aec209c94141dad7b7884f7be481a2f0d6d
+   8f9620a5b985a3a1dc4825f1f4c683457a98f799118691bc57b17ab42713b593
+   92c24c6920edb4f37e73dd795ac9bbfcd8035dba28421fce290109c222bfbc86
+   45bdcd99b590e64aeb5173c7538e77a7cd10a9d786338c43e3a0946b33a9c822
+   e0b86e6b4752ea2cae053b1bd897c6d749c7fa46308be876b8006c3ffa2d6479
+   6cb53b7769f0da52c697c8640c029099d84afb55c20c9ac84b959ff36c339e92
+   a21436f9a4c876375d16c41bd3780f024b867f6fe6394c5c64b4ea5a6f306c7e
+   93b40e751d291e90ec3adf902935285a5746781bfc1c594d520dc5828ba53d3f
+   6dc080d82251557b9804deeaae90bb1a45d9895c5067f3b04dbfcbb5ab0be3e2
+   22783694c9ab9d652dc216306ea4fc09734e90bd08625e688b9bc1b8c73e3366
+   078b0d30cc5fbb248a5e84a416a3d849772ef6eadf20f73eeb82125f68a216e6
+   83dd79bd150e5f7bf7a357236ed41ca06b8c40bcce840e118f6cf457ff151654
+   72169420815aa9a38719072be9c824d68a0cc5d6b4251ff9180938def3dcb0ac
+   63f1febc1579b537b71e1fd12687ec49885dbcf93db68f44660bca4780ca9aa8
+   dc337f8a3699ff549dfa26c1a5ddab43cdac7062d90fc2a779ff528c414035f7"
+    16
+    45bdcd99b590e64aeb5173c7538e77a7cd10a9d786338c43e3a0946b33a9c822;
+  "aa199ae7d7c298e11aa74e5bcff2f206fe6b53962f3bb39767ad6df19c58d93d
+   4b95d1e296609760e06e7e476af7182db41712d73be94a3533b7332a7dbb780d
+   b72f91cbf1117db1982b035f0e76e51bf4cd8e968b932606450bdae0d588906b
+   a1de9fc4d0e579aad319de0280fb45b5fed6c9d38dab5216ff8401376fce0230
+   fc216489a815b0c98969118c9ada3f7152c4eb07217abe54fae4fd4d63e96811
+   b660cb7ac499821dc872c3400fb2590527659ecd72df16c7ec5376075fca7d7e
+   3bbbd9dbbc9263d289de49b1648fd64751d8b0e6d5d506a356fee0ed6452ce89
+   d17efdc8cff826d28ab55b51211209a27054f2d33f108f34ce7bdc5c71b918e1
+   21da90e37be817920404ff5015346dd05ef32e018632e09b7cea35d42eb1de1d
+   66da40ef6fae8df49b5aca9a2400ea4fba527a9513c821e00985625615e71416
+   61e5b60766ca457b36aeca26a62e6f4831691ef79bdc72158c2a2b85fe3b5cb2
+   9a0917795f936a5384c4a504b2ba3d7056906ea4e34474c310b873f88890bd37
+   af65ade7e8f0022420932d50d0a8587c43ac4436bc511248358886e2c7072c1f
+   fadd2a9fa72f438f147964180ffba490beaa55baf6275d8ca347ce5f5f94fd05
+   debd9beec2527f284790a9ca8fbc074ec359f4a89974c2ff49780fcb21c5ea91
+   f6a57794ba1265d9974e52f856acd3dddd0f6a50844172466c82f0d49eef676d
+   97cbe03e723431b6c14bf1681e845d530e083ddaa26f055d3e162615f57c113f
+   b89054ac8b7135c1e6d215e4e5dcf679298fdcf6ef35301002be560389f8cd08
+   8ba6a9d5ee4bf15d87170e7c050699e858c6316bc92d5f4e19eeb3ed82e012b0
+   bf0f272aabf63cd98397f4da2fd3c5742373529c91ab455fdf394fb6d0b8272d
+   7a2a4980dec077abbd6a06f8b90219b818d4990b8f62b9dfc50bc4feec31eaf6
+   f1d55b4e207cf5b7bdff5f59a63b55fbce6704b5ace5c5183f6be8e4770c567c
+   d55b23bebc2f16fc9adddf06ece363add71c4cfd73ab228461cfb926addee0cd
+   76ac92ee62c2bb928bb5ec11673b51c2f1fec44ca27741a647cadfe55733eb41
+   1544a9b6c6cf77fec3e83bb08056bf18f3eb440611249f60cc97b58b5a93d364
+   702a0023d8ff6a108a2eadb777569f54df2c3b85634bb872611ccd8cf74e2807
+   8dc8889dae004e88a94f3c3beb4d39da7c074a038ff8899c5798f7a26fd17ec9"
+    19
+    bf0f272aabf63cd98397f4da2fd3c5742373529c91ab455fdf394fb6d0b8272d;
+  "63eca008f74f57babb34dde1fbaa5264656007f7479d8df3ba5cccadbe83925f
+   001a67bf61d077528bf9b386694a99d7293d6b49f368ad54767a2829643621b0
+   4c124850c332a4e2a6a335e5f5676f803ede7958719b083f648137cfccb82f50
+   39f293fdd5b28c882b824d1cfef38a327334776139bc2d814834a86d6b2d93bf
+   114df0c93aebb6a764740e43a67c6b582b49f6d0c393a23db42611023c044d9a
+   cd9e11bd49d7ee82e52f89d7100fd64c4474695054cd22442ed2bf17991cebe8
+   56931f05328bd38dea431af6537fe4a4f1e419a24c5181974e61b64367a65a5b
+   2bec95a108b7a500937b5a3f3c54ae9b2cc7b11629ac581f7d8663b9c910af96
+   380777fd3ab97d140a142d3d37c7786264ea00b63083219652376d7fd56ea846
+   f0fb2846d9cb0b88751db963f9360ff2bda25052eba9edd2ec561807c1f0fc27
+   34294c58ff5ff91f1472dc3d7b3099c81ef434126c58de3751c788a71f2a78de
+   05c5a1c0bf29c1bef5da9298450b8ce6c5856b3f7e2037133734a03959573927
+   7fd9db5b2418267e94db49ea0534ec8d397f32f90981448c944a4ff3cb6d9c3f
+   7015d096ddd557e669fcedd9b3b2624b910505f756e8ea160c5436bab604669b
+   46858fe7612b43ba805a6c7999a3be02b1e635963792d228f1414fbdf13e175b
+   70422706d36540ece562d1c36bfc5b178d1cf47c1ed87bea38be5a9f95010521
+   250e48d385aefbc10776582e71e4139148c99d6f9ea8c46a8e57194986eb2ef8
+   44accaac045de3183f7a45f89d4bdb5534594c90296ea664061f3f8a142f2d7e"
+    9
+    f0fb2846d9cb0b88751db963f9360ff2bda25052eba9edd2ec561807c1f0fc27;
+  "3fca772e14531611cf82782ecff97358f710763698b73e84479056a97d7d352f"
+    0
+    3fca772e14531611cf82782ecff97358f710763698b73e84479056a97d7d352f;
+  "fd8d6560ef50712fb5f0707c342f618cbbe5697d261d249ad4887dc5ebac4f07
+   89c98bc89a81402e218e377257bd1532d524dd33a3b8c0458b2e5211d4d7b305
+   e48938f9271a8861d46fa6063563b92c0a6fd59634151b075316faad9c87008e
+   332fb871bf280cb18dc5d444a565ab1e505d274e52c231808af7d52cc28990de
+   9073abe824ac2d30ec9562a5a67836af5cf9c038aee85ae1f7d387da64f558d5
+   04c3ffe8e6ed014162fbe6f3b8467114afdb6d5d51ad878c4462d8a926d9966a
+   5864d08abd45dd3d4b6e59762a8feb76cdbcbab01a66e512d40bc070e2754ce9
+   0a780e6ecd9b4ed16cb4fd1b4b060c74d97a4268733855102b036f89cb4d5bac
+   34bddd4d2ac8a920864e6b9cff04ab70f9978a16d0ceb06aee33aaa78e49328e
+   b65e8424be6a9247ad08f01a28e887bca33b3f5c28ef3adebf37798972eb99fc
+   ebd2aa397fc49104dc1c3f82f275bf625984c8c84a6f699e801b736c667a8cb8
+   8a704e508538e1d8a64c4c9052f46a07151c79dcf95e6359a8e5f41370ba40e2"
+    4
+    a373abe824ac2d30ec9562a5a67836af5cf9c038aee85ae1f7d387da64f55855;
+  "fb1b4c61b9b2fbe2faa5c0e3227e3c2fd4c8277aa629fc88fc18a4a29df3d6f0
+   3431d240f65ae76dcca41df165a4eb4c5af155027844d80a0c7f0d07ca4b5761
+   67e879347f3adcd41cac36e8c80a0f4c2ea80eb08ae9ee2b21e528769eb4c7bb
+   ce843b0190451928f2e637449b5ed95580645a0e0440ab017026631c619d2bcb
+   cc85641974b86dfa780e3edeafc0d6730da6f579826ba8f9bb8ab065b1e149b7
+   2f0c812e2c9114bef4810a01d108ff001fe328d575cff750e30133b464e2648b
+   407a5a8964f840ca90aa4cf79a18f5760f7a8ff23bd6bf2d6dfc88c980728aaf
+   26c2b3f4075ede77023b2de230edf8ce5e75a0cb9f1d81a0d154ba5d79de83f6
+   cd98878185983eebc6f188559d9bbf8dc422eca6598a7df35449d0b39106c706
+   42aea74be96565c44c08df95a6aa58603085152d4f7fcf38375283859d17a46c
+   31383c1609e8be3dc7279916eb5bb5d3e95e745a96f55ed3d69f296bfda19a28
+   dc140f380ac16ab63124f9f7a02aa458ceeffbed4a9b8e31f45c67ce6ce1c394
+   81bb67da90b02b5b19ce9863902f12f33a85795994d7d22b914f0e82a44a4f11
+   fd76e39b1d68f07e538353c0ffeb0c1225f5de64166ccd419c10134329f954de
+   e9f40437c324cacfc6974bee082cdb82c432a86d8465a0229a1e05fb19dec82d"
+    0
+    0e1c4c61b9b2fbe2faa5c0e3227e3c2fd4c8277aa629fc88fc18a4a29df3d670;
+  "c2b1fe3853bbed5be05536475b2f1bb818eb5ed0111f3be6c6b3bb8ede2d0beb
+   a692dee2a40878814b9ded7ba7ba47a391585ac93af04a0addec3904ed912ec6
+   015e98f69b98f157f559f8282bfbd20e07cc4a9e2929feab5a8c246011d1098f
+   76761cf13e45886da2b747f0de3a238be8aaf5868eca88c4de6b614ff3902e12
+   b6b06a046fa5f2e43e698fc96818cc7bf888d5c4f4f2f0bda86cc35c1b48679c
+   d7ecabc614122bb6908ebabcf7bcfa9a4fae88bb8450d559297c778dd35279f8
+   cdd96bbd24cc00b4fa5c8b20efa66a3db1d62e76f001dbd87800fc59f4a29a1d
+   9c16ca817b43101672fd1cb3583a6b44bfe2ab5956794280a3a32bd2aa651656
+   4d7ba5f8240527b3c9de386b00dafc163314b3f1311bc30b8434993b50e08d67
+   c4ab9766eee58337a92412440f12083a0205c39ba27e0877613b4288dfce9899
+   71ca275f3f7df242b5770d37c92425bde86184ab23c06c6b6bec799c47651433
+   49da5429ec1ade01eba828ad21d230cced84c8a28f239a69194cc0b5de9a0f20
+   fc17ee1656b6f0de36158fe2db82ad3f63c196c54002728bde4c5e27e6c0d7db
+   ece944bcc82f520e8171aefe728863b99a9772cc48b714d82426224b302b7be2
+   d2ea262ae062bc1167e79a7bd8abc2b6c7cbbdc03622495d1ff3a56e23c03f72
+   9be5176e8e873f9c320cff256e7b8801cdc1cee0b32ddd715d71abeaf909e0bd
+   0e666632a0ea9c9c5cc3fa519a42c34313ed2f64057106e38dddec87d68146b0
+   dc48385d46bcedbdf17f43e7b2de274556b411a0ac4b7e89a2f5f71a1d1ea5ba
+   76919d83ecc757cfcd916e23e5cadbdda21793a322c0fadad4e581819ebc0b18
+   84830e7a1b4b50e6ba90fd5f8b1198aa60b0c8987c962e9eb12adc2cc389ee1d"
+    11
+    49da5429ec1ade01eba828ad21d230cced84c8a28f239a69194cc0b5de9a0f20;
+  "99f065bb53134babd50f3f46adb63c64f7600acb39487718bc0a39fd3a5f4ebd
+   f70702612b9b45f7833232a7267492299c23caeffdc4f8a494653cde777861ab
+   16c9b6b125cb9cbb201cd0a558fd58cc29f2d197b9b160a0cff88ac890b9e429
+   ff87c5e3356c8fb8dbeb739aaedd0df3da2ec3072e5a806569a5847fcbcb4267
+   01d23260fa58bc7c077e05cac9e1359a9f4f2c9f2bc8312e0832376e3c3cc554
+   b7b5071166d68c704410d4e9123a261631822060c336b8cf0f5685a7df6ae6ea
+   621633e25b1ba392baaa31fc2d6a57e8286f6bf6e5edd5a0268a895af91d61c8
+   a29ab1d52fde5e7026124c3cec2be1fa674d37692165f46d1d91bb9f41156a55
+   26d8eb53078f2e515bdee3adc377a16b54ae575343888c27c6d72e07dd7ded04
+   ba5d57dae01659afb41b3b4712f0ccfa3b6b2a0d8a99fa5f1078203925897618
+   8cf51cab05199e2154a5bf655e6a9e9498c20cd08b564936b164b0a7f49a1e30
+   c5b3977228539a7f573c88800633f1da39a3f1bff9e1018af48f94f211a812b3
+   149a93a1ded07e398fe248962a7656f9b0f15ce62c4aa0bba4a3c6f00cc362f7
+   234974b4054622b0672626f111ea5b44afd81dcb15f29974585c9b77476d9290
+   4be4b2338d92909e6a138d4d2e53e72707a4af62acc8cf2a121c8105ec4ebf32
+   1e6192c030263e3847898afaf5003000552b9ccba7caf6361c1f34fa0890b086
+   ba698e634085f7dd38da012c8c97efb97a9b3c08c829d660e72e46d12eba79ea
+   712198efd6734fb564278f1bd0dde082482078548dcf4681e65e6dce39328c1e
+   8cff8caee2ed08e384331fc0509c1ab44b291d840d19ee991c9978bb7642b4c7
+   98a539cf588938c8ee31d80ff0254e13460f50d7907885f2debf7b68be91edf0
+   f0cc67c038324ed37948dfd94ab50dc6fd07ea8b441009ea2c4e185f0d800b85
+   09ae723e872da1687e02c883a254e033e8c67e784ed33e3a28eb8cc92be37d32"
+    6
+    751633e25b1ba392baaa31fc2d6a57e8286f6bf6e5edd5a0268a895af91d6148;
+  "97379391993ac07a0b019c4b6d2d08d4555e5761b4faa7bea8eac269844c6106
+   a2aff4f6141eedf254a8f7122ee37a1403b97fddc2805ce4ad010829aee1575e
+   a54665a1ac19c8ab83dad06bb5ce855b45246a9ad338516c5d67948f86eb1aa7
+   b8fa1fa064f6bd0af94d427686a09472b6a841576754500464ac3310cc147d40
+   dbb4cd734b211f5ad48452a193489fa25b0c82a594105a96ad627c5cd5328596
+   5396b8de36ade038e4424344fb2083226410f771c8ec979e916f37710b56cffe
+   039b59e759c9a380200b129e08d77ef53d703689b60ba5f117111ddd27f1674a
+   b3456d7bfa566b925ef014c6538c89251b7c0fa9fea89fd1806f97bcbfc3cdb7
+   4ab7a386cbc720b5676de0e76d584d6fa538a0015debe30c37e1839165763d5c
+   f7f55c12c67c1ca28b3947fb7bd7c4ed9a5240f962425b9b4810191d448af7c5
+   8dc0a95877c2ea17052b55c9f93440319ec38bbf80b375177e84ad14bab558dd
+   246d97123750b41e5bf2d96f10b3c9e66e92759373999bd94191a65f25a864f3
+   5bfa2905cb0b0aef125fb39deb2cd392b3cfe3f3ec58f8361e8cd5f12bd2db98
+   192413efd53bb958417f65a818d48d6bbf94dcc77210d9623adbca15633bd7ad
+   ee95faf7a7f31c7afd13d393ff2ff4e448799c87c62092e9e646efa4c635d1f4
+   77c00984400bbdcc81aeb42085c44be70137db5a0464f6081aa9c8e646e96e1c
+   743cd93d6f6a48161881d2224b7d7c0ce96d56d54adff0b719955cde417b35a6
+   92b99335dcf6b33de126d05329d8884802cc3afd0f93e9dea7db5f6dbdc6c623
+   584ccd19fe7395f9f2dc53f2a9da292e0cccfabe82bc46aa64c29581fc570deb
+   f9321c751abb9df278fbc2054e3fa368734cc852589891b49580332a52b6bf72
+   debc2bf3cedb7c897924936aac0b485bc05eb89530c886299e8d1ccad277355a
+   472d49f8ccc249b8271fd0630ab575721852e98015ea27732915ed06775b444e
+   7b29b054a2347baeda4dbd1b739072e6d144aae3547adc8287c3af84285057d1
+   d7a79b1f1ca757e17729436fe744ea7d99a64d13bf85737b6a71d41ab13343e4
+   a957b6345193173a231d9db8acb3a6c09bb411d210e0e52c94e75a4d68602aba
+   6277d818cbecae95f1aea85481ee631ff1e7c77c6693e6349d1804db784238f2
+   27e1d5a11dd9025508168d9d11cce0b8f0768b6846105161eca53abfa4aeeff6
+   1823372e2c7cb9fdcdc97ca64ffa06564907b09015472cfa73bf0a45d7c90bec
+   08cfef24b9eb875598779315de4fcfc918931e05f49b374113c25cb5b23a4944
+   3a5d9db56bac2f413a3d33b6d7a2f54053aa3a641d6554d6f008779939f2682f
+   22d0256cb1a53aaefd5d2fde14b63e5adce607ee5a22e8498f29982f88088938"
+    18
+    6b4ccd19fe7395f9f2dc53f2a9da292e0cccfabe82bc46aa64c29581fc570d6b;
+  "91a76b64122a404fbf873d65089a7613bd3d93c4227a4b05817223640ec20ee9
+   ab46f7649122de1d73278608e02d44a1367f4f5a7c01d1c17f2a50fb3148dfcf"
+    0
+    a4a76b64122a404fbf873d65089a7613bd3d93c4227a4b05817223640ec20e69;
+  "1c12d157172079be7ecc31716fac8946f5517a3da6612bf4a0db65707e72764b
+   9d9ec126bd404e82448a16c187152307ab6319fdd5d4280f070275cedf1cced2
+   25be86a2abbf7619f7b92855cc50572af4fcf6ee071078d24baa24d623ebe4e5
+   9b3a13dd1b67a284a9ed869de2663d82035342bc0cad65484da1c7b60b82a55b
+   fb82840bfd348ccaa0d3d362c1123096a5103a09f979e2f4acdf7aa600e55a84
+   c64642a4946ed50924eb1a4c6ab73b53942c5a17cc868f8c6c5ef92ce5986830
+   8e7aaf58bc15be92a31af4f0b092969a250222e7ccbdb638aa846f8253c33d50
+   375bb009118659c831591bd6861e9c9eaec85c0fd9a1facd5f2767ff27e3d36f
+   f5b4b72840ef438fb8f7fd1419aa5248dc38126cfc29099cffe68aa94b215b31
+   3b0cf55a0dc7856788375bfa1390fe4c628c271c99ea76ac78517ad5f36f61ac
+   82cf74084903490f30152c730970f8b622de5414e1a60e1efafc6aa57ff2fba3
+   9d476226e3c4f844f392e7efea7726b02bea64c9aa1e78513efb28a000cf9624"
+    11
+    9d476226e3c4f844f392e7efea7726b02bea64c9aa1e78513efb28a000cf9624;
+  "4f8b3919461d4408a4d4375688f8985332745cb5253671dd7fea3c58b8e33e5b
+   ecd4f6bf71be54fa88e51fd9d98f60c009fa1b4f15ccacdfa7b26a5ba52b1794
+   b0bc276ac01ed6b25fb569ec8c614f4a9299faadcb93bdee4dc637c888381d29
+   2fbc1564ecd906f5d56838c9ceb3ba5b5f13925cadd653008f1ee9f54c18ea37
+   66e9f3ed35f45675f9601181ddcff688229371c6428c1d9dc67699821e3130b6
+   6b08a213ca51403db7e08bf6945b23ccb62465f582248661b901b6e550345516
+   abdb83672459dad5b11c3cf9e4d21235ff92c01ab00b2d44aa6f10bfe9b274d0
+   f609191b4efb288359af7170acd0904c57d45c7c658c0d670e0fb22f9ebc0044
+   e4056ab4b8afad5e6951c8168477f15ee3e11fe3f236a1d19ea201f78b8898a5
+   f3b253fd18515ee3dcfd4a14409838a3d993a5274bd77a1e5a7088d20ba6c592
+   710b8819a202ab80bcf308aa94d3305944dc739e33648df045bba215160f8ee9
+   1b63314e9fbd605ac063546ee4249bf9f37da0b6b78d99848f487c6880f70c3e
+   fb04f3e49a44c4eea104c213446b0e6b81da047a0862604f488e0c6128238d3c
+   43b1624809a253f46b12d97aa08dc3f16b25613022483b8044cb01b6d23cfb28
+   0796291d8916b0b70ebdab0f42b8cc55c14734cf7a398d48f94b48d9871ff0c2
+   c55cc772bb71392f13258339eaa1d8b01c402e8f6c9b6061f0e1c564feb98234
+   882ad3994d999ac7243ebe9955468a52b2242564a295a9740af8980043f9ef0a
+   201f86fc5826d74580c3bd3fe04cda2a823c2a4d1ace3e862a9bf6873ba25055
+   5c39347c213f6e1b5ded1de9f92ed21d99721c4e4216d5abe207321caa426971
+   38ba53a577809f2d2c3cc33016e6141f4a87b6f57b75be70b9cd3d287f07ab00
+   7b9e12c5293fd99ed3fb50a2eac4587bca4aa8bb97c147626dcb9688593ad2e9
+   4852c30283c1ffa109aade1353d11e9712d8c4e6d416926f231a2b89b78fbdbd
+   80d25270ef8002232cd0e35433ecefc135cbcaa06511ba3ac14484b6e41c953a
+   6159366a1aee4692a9986a12234728c685cf766ad3e2c4cc842f1142c0fb856e
+   95d34152d18b9942bb13c6bec8e533c259adfd69dbeb06da63c351997463cee9
+   dd5890be52cd0207fecd0f93dbd3a6819aa2c5a592ca0975a419104e7ff4c284
+   d9c3f02b7644b3580d190f03bfc9accc8abf9546463a2171d9cb19b3783e0c92
+   e59449e7a9d07631450d85d108f3cfec2d67d63ad65a7311b310bb10137fcdbc"
+    27
+    f89449e7a9d07631450d85d108f3cfec2d67d63ad65a7311b310bb10137fcd3c;
+  "e5d98efcc2879f32793efa8f96dda9c87b70834fc9d468dc464b0940a7dc160b
+   04d4bc5cd4690a0c6561feae82c6be57195c7553276f12aa16fb930ac47e315f"
+    0
+    e5d98efcc2879f32793efa8f96dda9c87b70834fc9d468dc464b0940a7dc160b;
+  "bfbed3f0a31b886bd96a817e0b65be1b1e374fddb237514e89fee7ce34a08c45
+   eedd85cd817fc74938e60c366445e6bd5383dedd290db3633d5ed2ff320139a2
+   006b1e62b3aa1830de71c0ae063fbf090e536304d601e6c851800ff1d501d249
+   a4a63dcc680646b69c8e651dd9c3e043bad07eb9bd6b55bc5bc854d82bbc6b00
+   ffa2e97c95ef5efb87b78e89f35e95f89c1c1b2591673fd2166fcc9765abb4b8
+   030984d84d3d9667e436996578a3ae58853d44e111990221cd15795167475426
+   da8350e83ac6d67029c24a8d386c6352a27bd22fd6a207474a952742790e4be9
+   0618b6f82b936b5eca87e9ab8dcd9a2e3744586bae01a75cfabb23b1b64f7aab
+   5a3e077d0d0d28ba3b6d6fefecc6c2f7ca530fa63bf414976ac8b26ed6596a3b
+   381e56750672340b18b60612bd462ade52d3b0d5b487f1af8438140740df484a
+   65275cc865fc4b5d94023fdcb929dd27dcd64870773c79f015d4a5f30751ef2f
+   724f96fe61888b5a885713d0c52e759726b877031b3f4f80ad24bcf417a3dbba
+   17f55299b7cd1d851091052401612078978bf2b09fca8c9e2189474e9d24b81f
+   14b82eebd7325586c1ed8be9353fe5ad9375290a92e76d13947c6405febb2f52
+   eb5a5c7771ccf698a2e803a3a4e6db056ceb0da4d808db5758f2cb28ccc44bee
+   96db7bfd64b7d41430ca6fd0714487926d02dc71571161f8deea0f6a3b52ba80"
+    6
+    ed8350e83ac6d67029c24a8d386c6352a27bd22fd6a207474a952742790e4b69;
+}
+
 condswap {
   14e55571df646a69a8280bf8dbf8e9afc15bf5558bb8b8236ebcaa19a96053bd
     8bef5021598a8175565e1f2b522ed1c4306fef4e0e973b50d3a03db1fcf11a43
@@ -439,6 +1007,79 @@ inv {
     0f5ccf4920d617c9b4f7fe6e2c9e95e89b5516555d5e3f5f9900485451d7425f;
 }
 
+quosqrt {
+  18798551568191dbfe6bcacf95bf4bf00290de4c773a1d4233d1eae272b3085b
+    2ee52110807ab6e31e0ed7b4de818d6474b514c63c99206e58a6df38e149123f
+    3819accb91d97a3f4dbca732f19723fc772a19b3eb4d307acad706cc7c7e1c1f
+    b5e653346e2685c0b24358cd0e68dc0388d5e64c14b2cf853528f9338381e360;
+  8671a0ecb7344f2e44fc9066aeb42661e848417e8c51b353680573830857d90f
+    9c4cfb1aa650924ceaf3e23b260d02b7d8b7dd4445360cad0bd4270428f55292
+    "" "";
+  bb0d27e1743f444e2f612c2ff575c6c6663f01869eaa8666774b8baa59b2a714
+    2fecb156c393d27d7b9a5e4cc2b57cb5524d5b945e92c5b4bdccdd6d00e684c6
+    "" "";
+  59af963f7245901807a46a59d4e49bab5b1fdf3001f63ef4e600ef8150d0e13a
+    b5ac3372ca5435577c416ba46a57879b0ca1df29057c540cac4edacc507b5e23
+    "" "";
+  a7b8659775a53e1fa315066be6a37a3f645d782cb69ec6b4f27fcf4daed3d82e
+    4550c4697a5d29d1a97b50ea65e98ec839567a3fc556ec3790b016c24b867d89
+    a190875f536f94ae2af8aae90bf0afabed437b36cf640d85529b150155eed53e
+    4c6f78a0ac906b51d5075516f40f505412bc84c9309bf27aad64eafeaa112a41;
+  7163512100699c32d5fadbe3583f2f6f314c347f1e66c434b15ac06a5733f3ed
+    2806d76598a43c24820daaf87afa5a9a4d414e5d8f51993f1b01166bb5479c27
+    01d5d023a6c5f7ec1d5df3179bb240e3003a9e3be8ad4e154c6e8f7cb7af6536
+    ec2a2fdc593a0813e2a20ce8644dbf1cffc561c41752b1eab391708348509a49;
+  e950533666a4a1edc3dae30637d6b005e34b614fe75555be0e1759def06a2aee
+    ac5a603347a585ca19eba141b1dd1b8833855e9807776627e8c9f92001a4b9b0
+    "" "";
+  d3c5ccb02442548901b3ffa2ed5564735b0b041386fd38e6c40844dc9183006e
+    5e6f23ccef94660e569bc42093d2b862ca605b81d64bb3589331d015082b4996
+    d7d578a72f1ea2dcacd0a96be285e9635230dc297fa7f6e1f2b9754e2d29190c
+    162a8758d0e15d23532f56941d7a169cadcf23d68058091e0d468ab1d2d6e673;
+  37cad075017c111f99135be6a0f553535d56153cef8839eee1e70614d65df1c2
+    e5f9944a377be3ab64daccfc9e711f4aa522c68a80efd0a70c72cdd4507014b7
+    "" "";
+  85dedba748f478537d016f20b9871e830e513514fbd27141aa54ca77b2a673be
+    950bc6fb51f6d8c36b7ddc8cb28d9efd498690a46c57888b279de0e549e84c52
+    fb7871031556b171a25dfd0483f0e2ed8d24a8acc2d9fc201f42f0b892fd541a
+    f2868efceaa94e8e5da202fb7c0f1d1272db57533d2603dfe0bd0f476d02ab65;
+  d70f399a983c6ad48acca796d9106c5e7681f34bdf34248f6dc54620282bb327
+    cad23bcd1fb96331bc8139f2a8f21d24492e56a7b80e343a7002acc96a739454
+    ff70c5bffe08911fb5522b21beecfd80fb018f0afef24fe85cfb7e4a5024960a
+    ee8e3a4001f76ee04aadd4de4113027f04fe70f5010db017a30481b5afdb6975;
+  71ee96ced0b50bc560f2477a88ea2447573490f71850f084ae0b318cafd8a75f
+    15c61eefd2c05d72fb07e44a006dfe314d8797f978bab1fe9f9276bcc82b542a
+    "" "";
+  c27a9f169b8096308f313ab5a521886084f03ec6d9e8b30e4773d0a3ab1a7c67
+    a7ca0e7fc5566dfc3790a3de164ef26d6452715db428994d438e79f65034d174
+    129427bd4c2195fac5a0da4c52ff634c697f18c3b02d0e7aad45a64d03b6e922
+    db6bd842b3de6a053a5f25b3ad009cb39680e73c4fd2f18552ba59b2fc49165d;
+  dd73476aeab865af0775723ebd2128ca71621b1d95231813c3d3cb32b805f418
+    dc6621f2ba82deb8272243baa5d2e177a60b1b780daa3ba081040e05b1d1b2f9
+    32ae54f7a7dfa101bad00f723898d29a7307454f86cd1197c44b07d1b997fa1f
+    bb51ab0858205efe452ff08dc7672d658cf8bab07932ee683bb4f82e46680560;
+  3a3ee482bf7075fa38780616603133ecea7b56acab59d96ebf7192e21c49a806
+    b7e6d647792961137dadce55ce69634379338bbda45fbef9d56be52620738d06
+    122b696683c2d1f3feedaf6166037ddbd7281e0c4c875724177f240b54e0dc22
+    dbd496997c3d2e0c0112509e99fc822428d7e1f3b378a8dbe880dbf4ab1f235d;
+  71f31797a8a36123e4a0b173ee4bc5a04d7799d1eba246df51cf943aeba0270c
+    7340069440d6c72b4536018eec373f50a1142c9e79de8a5396f994e53c64ab18
+    "" "";
+  0d2a6a9de4d52289cc724840670abcc5a4ee04f1197bd1d230689431b01afce0
+    21457f6784da81822df90f09b44782bd50a12c4fb378091cd33b177c734e0728
+    2b272304b3cca59e26431d91118a95c965bd542191c7cef760b085673e96a432
+    c2d8dcfb4c335a61d9bce26eee756a369a42abde6e3831089f4f7a98c1695b4d;
+  288b09090258a71747c1a08a51b0894a0c096f5b88ee38ea56a3aaefc1afa0f5
+    a7f6391e06b8972b18e899753bf3853270cae7971774041fa9bf09a55349f950
+    "" "";
+  e912e39e2199c3980c5fe3cac6d8bed394367f28213524f006a9b2c0cce4a6dc
+    e6b4a592e37fb5d3af73c486cc211a57d4077c093a161276dcb6eb44303d3ec6
+    "" "";
+  ec6785be59b890e07176c09195430b7f5daee0b0898ee744e578ac25873012b6
+    b3cd2df2c2531beeca882607d73f38403d8ff384f99be1ce582536bc3d4bfcd1
+    "" "";
+}
+
 sub-mulc-add-sub-mul {
   ## A very basic smoke-test.
   03 01 5 01 07 02 37;

diff --git a/utils/curve25519.sage b/utils/curve25519.sage
index ec21d4b..8047aeb 100644 (file)
--- a/utils/curve25519.sage
+++ b/utils/curve25519.sage
@@ -10,6 +10,42 @@ def ld(v):
 def st(x, n):
   return ''.join(chr((x >> 8*i)&0xff) for i in xrange(n))
 
+def piece_widths_offsets(wd, n):
+  o = [ceil(wd*i/n) for i in xrange(n + 1)]
+  w = [o[i + 1] - o[i] for i in xrange(n)]
+  return w, o
+
+def pieces(x, wd, n, bias = 0):
+
+  ## Figure out widths and offsets.
+  w, o = piece_widths_offsets(wd, n)
+
+  ## First, normalize |n| < bias/2.
+  if bias and n >= bias/2: n -= bias
+
+  ## First, collect the bits.
+  nn = []
+  for i in xrange(n - 1):
+    m = (1 << w[i]) - 1
+    nn.append(x&m)
+    x >>= w[i]
+  nn.append(x)
+
+  ## Now normalize them to the appropriate interval.
+  c = 0
+  for i in xrange(n - 1):
+    b = 1 << (w[i] - 1)
+    if nn[i] >= b:
+      nn[i] -= 2*b
+      nn[i + 1] += 1
+
+  ## And we're done.
+  return nn
+
+def combine(v, wd, n):
+  w, o = piece_widths_offsets(wd, n)
+  return sum(v[i] << o[i] for i in xrange(n))
+
 ###--------------------------------------------------------------------------
 ### Define the curve.
 
@@ -45,6 +81,8 @@ def sqrn(x, n):
   for i in xrange(n): x = x*x
   return x
 
+sqrtm1 = sqrt(k(-1))
+
 def inv(x):
   t2 = sqrn(x, 1)        #   1 | 2
   u = sqrn(t2, 2)        #   3 | 8
@@ -70,7 +108,55 @@ def inv(x):
   t = u*t11              # 265 | 2^255 - 21
   return t
 
+def quosqrt(x, y):
+
+  ## First, some preliminary values.
+  y2 = sqrn(y, 1)        #   1 | 0, 2
+  y3 = y2*y              #   2 | 0, 3
+  xy3 = x*y3             #   3 | 1, 3
+  y4 = sqrn(y2, 1)       #   4 | 0, 4
+  w = xy3*y4             #   5 | 1, 7
+
+  ## Now calculate w^(p - 5)/8.  Notice that (p - 5)/8 =
+  ## (2^255 - 24)/8 = 2^252 - 3.
+  u = sqrn(w, 1)         #   6 | 2
+  t = u*w                #   7 | 3
+  u = sqrn(t, 1)         #   8 | 6
+  t = u*w                #   9 | 7
+  u = sqrn(t, 3)         #  12 | 56
+  t = u*t                #  13 | 63 = 2^6 - 1
+  u = sqrn(t, 6)         #  19 | 2^12 - 2^6
+  t = u*t                #  20 | 2^12 - 1
+  u = sqrn(t, 12)        #  32 | 2^24 - 2^12
+  t = u*t                #  33 | 2^24 - 1
+  u = sqrn(t, 1)         #  34 | 2^25 - 2
+  t = u*w                #  35 | 2^25 - 1
+  u = sqrn(t, 25)        #  60 | 2^50 - 2^25
+  t2p50m1 = u*t          #  61 | 2^50 - 1
+  u = sqrn(t2p50m1, 50)  # 111 | 2^100 - 2^50
+  t = u*t2p50m1          # 112 | 2^100 - 1
+  u = sqrn(t, 100)       # 212 | 2^200 - 2^100
+  t = u*t                # 213 | 2^200 - 1
+  u = sqrn(t, 50)        # 263 | 2^250 - 2^50
+  t = u*t2p50m1          # 264 | 2^250 - 1
+  u = sqrn(t, 2)         # 266 | 2^252 - 4
+  t = u*w                # 267 | 2^252 - 3
+  beta = t*xy3           # 268 |
+
+  ## Now we have beta = (x y^3) (x y^7)^((p - 5)/8) =
+  ## x^((p + 3)/8) y^((7 p - 11)/8) = (x/y)^((p + 3)/8).
+  ## Suppose alpha^2 = x/y.  Then beta^4 = (x/y)^((p + 3)/2) =
+  ## alpha^(p + 3) = alpha^4 = (x/y)^2, so beta^2 = ±x/y.  If
+  ## y beta^2 = x then alpha = beta and we're done; if
+  ## y beta^2 = -x, then alpha = beta sqrt(-1); otherwise x/y
+  ## wasn't actually a square after all.
+  t = y*beta^2
+  if t == x: return beta
+  elif t == -x: return beta*sqrtm1
+  else: raise ValueError, 'not a square'
+
 assert inv(k(9))*9 == 1
+assert 5*quosqrt(k(4), k(5))^2 == 4
 
 ###--------------------------------------------------------------------------
 ### The Montgomery ladder.

diff --git a/utils/qfarith-test b/utils/qfarith-test
index 3904d42..45f233f 100755 (executable)
--- a/utils/qfarith-test
+++ b/utils/qfarith-test
@@ -73,6 +73,9 @@ def add(k): binop(k, lambda x, y: x + y)
 def sub(k): binop(k, lambda x, y: x - y)
 
 @test
+def neg(k): unop(k, lambda x: -x)
+
+@test
 def mul(k): binop(k, lambda x, y: x*y)
 
 @test
@@ -82,6 +85,15 @@ def sqr(k): unop(k, lambda x: x*x)
 def inv(k): unop(k, lambda x: x and x.inv() or k(0))
 
 @test
+def quosqrt(k):
+  x = k.rand(); y = k.rand()
+  yy = +y
+  u = yy and x/y or k(0)
+  try: zz = u.sqrt()
+  except ValueError: print '  %s\n    %s\n    "" "";' % (x, y)
+  else: print '  %s\n    %s\n    %s\n    %s;' % (x, y, zz, -zz)
+
+@test
 def mulconst(k):
   x = k.rand()
   a = C.rand.range(1 << 20) - (1 << 19)
@@ -90,6 +102,23 @@ def mulconst(k):
 def mask(): return C.rand.range(2)*0xffffffff
 
 @test
+def pick2(k):
+  x = k.rand(); y = k.rand(); m = mask()
+  print '  %s\n    %s\n    0x%08x\n    %s;' % (x, y, m, +(m and x or y))
+
+@test
+def condneg(k):
+  x = k.rand(); m = mask()
+  print '  %s\n    0x%08x\n    %s;' % (x, m, x*(m and -1 or +1))
+
+@test
+def pickn(k):
+  n = C.rand.range(31) + 1
+  v = [k.rand() for i in xrange(n)]
+  i = C.rand.range(n)
+  print '  "%s"\n    %d\n    %s;' % ('\n   '.join(map(str, v)), i, +v[i])
+
+@test
 def condswap(k):
   x = k.rand(); y = k.rand(); m = mask()
   xx, yy = m and (+y, +x) or (+x, +y)