Test elliptic curves more thoroughly.

[u/mdw/catacomb] / ec-bin.c

diff --git a/ec-bin.c b/ec-bin.c
index 42aaad8..a71ed2d 100644 (file)
--- a/ec-bin.c
+++ b/ec-bin.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: ec-bin.c,v 1.3 2004/03/22 02:19:09 mdw Exp $
+ * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
  *
  * Arithmetic for elliptic curves over binary fields
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: ec-bin.c,v $
+ * Revision 1.4  2004/03/23 15:19:32  mdw
+ * Test elliptic curves more thoroughly.
+ *
  * Revision 1.3  2004/03/22 02:19:09  mdw
  * Rationalise the sliding-window threshold.  Drop guarantee that right
  * arguments to EC @add@ are canonical, and fix up projective implementations
@@ -82,8 +85,33 @@ static ec *ecprojneg(ec_curve *c, ec *d, const ec *p)
 
 static ec *ecfind(ec_curve *c, ec *d, mp *x)
 {
-  /* write me */
-  return (0);
+  field *f = c->f;
+  ecctx *cc = (ecctx *)c;
+  mp *y, *u, *v;
+  
+  if (F_ZEROP(f, x))
+    y = F_SQRT(f, MP_NEW, cc->b);
+  else {
+    u = F_SQR(f, MP_NEW, x);           /* %$x^2$% */
+    y = F_MUL(f, MP_NEW, u, cc->a);    /* %$a x^2$% */
+    y = F_ADD(f, y, y, cc->b);         /* %$a x^2 + b$% */
+    v = F_MUL(f, MP_NEW, u, x);                /* %$x^3$% */
+    y = F_ADD(f, y, y, v);             /* %$A = x^3 + a x^2 + b$% */
+    if (!F_ZEROP(f, y)) {
+      u = F_INV(f, u, u);              /* %$x^{-2}$% */
+      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$% */
+    }
+    MP_DROP(u);
+    MP_DROP(v);
+  }
+  if (!y) return (0);
+  EC_DESTROY(d);
+  d->x = MP_COPY(x);
+  d->y = y;
+  d->z = MP_COPY(f->one);
+  return (d);
 }
 
 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
@@ -306,7 +334,7 @@ static int eccheck(ec_curve *c, const ec *p)
   u = F_ADD(f, u, u, v);
   v = F_SQR(f, v, p->y);
   u = F_ADD(f, u, u, v);
-  rc = F_ZEROP(f, u);
+  rc = F_ZEROP(f, u) ? 0 : -1;
   mp_drop(u);
   mp_drop(v);
   return (rc);
@@ -369,12 +397,12 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b)
 
 static const ec_ops ec_binops = {
   ecdestroy, ec_idin, ec_idout, ec_idfix,
-  0, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
+  ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
 };
 
 static const ec_ops ec_binprojops = {
   ecdestroy, ec_projin, ec_projout, ec_projfix,
-  0, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+  ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
 };
 
 /*----- Test rig ----------------------------------------------------------*/
@@ -394,16 +422,16 @@ int main(int argc, char *argv[])
   printf("ec-bin: ");
   fflush(stdout);
   a = MP(1);
-  b = MP(0x066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad);
-  p = MP(0x20000000000000000000000000000000000000004000000000000000001);
+  b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f);
+  p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001);
   r =
-  MP(6901746346790563787434755862277025555839812737345013555379383634485462);
+  MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770);
 
   f = field_binpoly(p);
   c = ec_binproj(f, a, b);
   
-  g.x = MP(0x0fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b);
-  g.y = MP(0x1006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052);
+  g.x = MP(0x15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7);
+  g.y = MP(0x061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706);
 
   for (i = 0; i < n; i++) { 
     ec_mul(c, &d, &g, r);