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

diff --git a/math/ec-bin.c b/math/ec-bin.c
index c7fe96d4..598b7e3c 100644
--- a/math/ec-bin.c
+++ b/math/ec-bin.c
@@ -317,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;
@@ -380,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 ----------------------------------------------------------*/