math/ec-prime.c: Some (ineffective) optimization work.

It's possible to trade off a multiplication for a squaring in the
projective doubling case: computing 2 y z = (y + z)^2 - y^2 - z^2
(because we already have to compute y^2 and z^2).  But for some reason
this doesn't actually make things any better.

diff --git a/math/ec-prime.c b/math/ec-prime.c
index c2ec288..8a11037 100644 (file)
--- a/math/ec-prime.c
+++ b/math/ec-prime.c
@@ -104,17 +104,20 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
     field *f = c->f;
     mp *p, *q, *m, *s, *dx, *dy, *dz;
 
+    q = F_ADD(f, MP_NEW, a->y, a->z);  /* %$y + z$% */
+    dz = F_SQR(f, MP_NEW, q);        /* %$(y + z)^2 = y^2 + 2 y z + z^2$% */
     p = F_SQR(f, MP_NEW, a->z);                /* %$z^2$% */
-    q = F_SQR(f, MP_NEW, p);           /* %$z^4$% */
+    dz = F_SUB(f, dz, dz, p);          /* %$y^2 + 2 y z$% */
+    q = F_SQR(f, q, p);                        /* %$z^4$% */
     p = F_MUL(f, p, q, c->a);          /* %$A z^4$% */
     m = F_SQR(f, MP_NEW, a->x);                /* %$x^2$% */
     m = F_TPL(f, m, m);                        /* %$3 x^2$% */
     m = F_ADD(f, m, m, p);             /* %$m = 3 x^2 + A z^4$% */
 
-    q = F_DBL(f, q, a->y);             /* %$2 y$% */
-    dz = F_MUL(f, MP_NEW, q, a->z);    /* %$z' = 2 y z$% */
+    p = F_SQR(f, p, a->y);             /* %$y^2$% */
+    dz = F_SUB(f, dz, dz, p);          /* %$z' = 2 y z$% */
 
-    p = F_SQR(f, p, q);                        /* %$4 y^2$% */
+    p = F_QDL(f, p, p);                        /* %$4 y^2$% */
     s = F_MUL(f, MP_NEW, p, a->x);     /* %$s = 4 x y^2$% */
     q = F_SQR(f, q, p);                        /* %$16 y^4$% */
     q = F_HLV(f, q, q);                        /* %$t = 8 y^4$% */
@@ -138,6 +141,8 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
   return (d);
 }
 
+/* #define USE_SQUARE */
+
 static ec *ecprojxdbl(ec_curve *c, ec *d, const ec *a)
 {
   if (EC_ATINF(a) || F_ZEROP(c->f, a->y))
@@ -146,16 +151,31 @@ static ec *ecprojxdbl(ec_curve *c, ec *d, const ec *a)
     field *f = c->f;
     mp *p, *q, *m, *s, *dx, *dy, *dz;
 
+#ifdef USE_SQUARE
+    q = F_ADD(f, MP_NEW, a->y, a->z);  /* %$y + z$% */
+    dz = F_SQR(f, MP_NEW, q);        /* %$(y + z)^2 = y^2 + 2 y z + z^2$% */
+#else
+    q = MP_NEW;
+#endif
     m = F_SQR(f, MP_NEW, a->z);                /* %$z^2$% */
+#ifdef USE_SQUARE
+    dz = F_SUB(f, dz, dz, m);          /* %$y^2 + 2 y z$% */
+#endif
     p = F_SUB(f, MP_NEW, a->x, m);     /* %$x - z^2$% */
-    q = F_ADD(f, MP_NEW, a->x, m);     /* %$x + z^2$% */
+    q = F_ADD(f, q, a->x, m);          /* %$x + z^2$% */
     m = F_MUL(f, m, p, q);             /* %$x^2 - z^4$% */
     m = F_TPL(f, m, m);                        /* %$m = 3 x^2 - 3 z^4$% */
 
-    q = F_DBL(f, q, a->y);             /* %$2 y$% */
-    dz = F_MUL(f, MP_NEW, q, a->z);    /* %$z' = 2 y z$% */
+#ifdef USE_SQUARE
+    p = F_SQR(f, p, a->y);             /* %$y^2$% */
+    dz = F_SUB(f, dz, dz, p);          /* %$z' = 2 y z$% */
+    p = F_QDL(f, p, p);                        /* %$4 y^2$% */
+#else
+    q = F_DBL(f, q, a->y);             /* %$2 y% */
+    dz = F_MUL(f, MP_NEW, a->z, q);    /* %$z' = 2 y z$% */
+    p = F_SQR(f, p, q);                        /* %$4 y^2% */
+#endif
 
-    p = F_SQR(f, p, q);                        /* %$4 y^2$% */
     s = F_MUL(f, MP_NEW, p, a->x);     /* %$s = 4 x y^2$% */
     q = F_SQR(f, q, p);                        /* %$16 y^4$% */
     q = F_HLV(f, q, q);                        /* %$t = 8 y^4$% */