X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a..HEAD:/math/ec-bin.c

diff --git a/math/ec-bin.c b/math/ec-bin.c
index d91b0343..598b7e3c 100644
--- a/math/ec-bin.c
+++ b/math/ec-bin.c
@@ -73,6 +73,7 @@ static ec *ecfind(ec_curve *c, ec *d, mp *x)
       v = F_MUL(f, v, u, y);	    /* %$B = A x^{-2} = x + a + b x^{-2}$% */
       y = F_QUADSOLVE(f, y, v);		/* %$z^2 + z = B$% */
       if (y) y = F_MUL(f, y, y, x);	/* %$y = z x$% */
+      /* Hence %$y^2 + x y = (z^2 + z) x^2 = A$% */
     }
     MP_DROP(u);
     MP_DROP(v);
@@ -316,6 +317,32 @@ static int ecprojcheck(ec_curve *c, const ec *p)
   return (rc);
 }
 
+static int eccompr(ec_curve *c, const ec *p)
+{
+  /* --- Take the LSB of %$y/x$%, or zero if %$x = 0$% ---
+   *
+   * The negative of a point has %$y' = y + x$%.  Therefore either %$y/x$% or
+   * $%(y + x)/x = y/x + 1$% is odd, and this disambiguates, unless %$x =
+   * 0$%; but in that case we must have %$y^2 = b$% which has exactly one
+   * solution (because squaring is linear in a binary field).
+   */
+
+  int ybit;
+  field *f = c->f;
+  mp *y, *t;
+  if (MP_ZEROP(p->x)) ybit = 0;
+  else {
+    t = F_IN(f, MP_NEW, p->x);
+    y = F_IN(f, MP_NEW, p->y);
+    t = F_INV(f, t, t);
+    t = F_MUL(f, t, y, t);
+    t = F_OUT(f, t, t);
+    ybit = MP_ODDP(t);
+    MP_DROP(y); MP_DROP(t);
+  }
+  return (ybit);
+}
+
 static void ecdestroy(ec_curve *c)
 {
   ecctx_bin *cc = (ecctx_bin *)c;
@@ -379,13 +406,13 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b)
 static const ec_ops ec_binops = {
   "bin",
   ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
-  ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
+  ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck, eccompr
 };
 
 static const ec_ops ec_binprojops = {
   "binproj",
   ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
-  ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+  ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck, eccompr
 };
 
 /*----- Test rig ----------------------------------------------------------*/