ec-bin (ec_binproj): Make curve setup faster.

Rather than computing bb from b by two square roots, each of which
actually calculates sqrt(x) as x^{2^{m-1}}, we can save time by
computing qdrt(x) as x^{2^{m-2}}.

I think this means that nobody uses F_SQRT on binary fields any more,
but I'll keep them around just in case.

diff --git a/ec-bin.c b/ec-bin.c
index 1a70fe2..e84252c 100644 (file)
--- a/ec-bin.c
+++ b/ec-bin.c
@@ -353,19 +353,28 @@ ec_curve *ec_bin(field *f, mp *a, mp *b)
 ec_curve *ec_binproj(field *f, mp *a, mp *b)
 {
   ecctx_bin *cc = CREATE(ecctx_bin);
 ec_curve *ec_binproj(field *f, mp *a, mp *b)
 {
   ecctx_bin *cc = CREATE(ecctx_bin);

+  int i;
+  mp *c, *d;
+

   cc->c.ops = &ec_binprojops;
   cc->c.f = f;
   cc->c.a = F_IN(f, MP_NEW, a);
   cc->c.b = F_IN(f, MP_NEW, b);
   cc->c.ops = &ec_binprojops;
   cc->c.f = f;
   cc->c.a = F_IN(f, MP_NEW, a);
   cc->c.b = F_IN(f, MP_NEW, b);

-  cc->bb = F_SQRT(f, MP_NEW, cc->c.b);
-  if (cc->bb)
-    cc->bb = F_SQRT(f, cc->bb, cc->bb);
-  if (!cc->bb) {
+
+  c = MP_COPY(cc->c.b);
+  for (i = 0; i < f->nbits - 2; i++)
+    c = F_SQR(f, c, c);
+  d = F_SQR(f, MP_NEW, c); d = F_SQR(f, d, d);
+  if (!MP_EQ(d, cc->c.b)) {
+    MP_DROP(c);
+    MP_DROP(d);

     MP_DROP(cc->c.a);
     MP_DROP(cc->c.b);
     DESTROY(cc);
     return (0);
   }
     MP_DROP(cc->c.a);
     MP_DROP(cc->c.b);
     DESTROY(cc);
     return (0);
   }

+  cc->bb = c;
+  MP_DROP(d);

   return (&cc->c);
 }
 
   return (&cc->c);
 }