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);
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;
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 ----------------------------------------------------------*/