From f69ab683f8d4d795443533c60cd1531fa211ab15 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Fri, 27 Dec 2013 12:13:47 +0000
Subject: [PATCH] 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.
---
 math/ec-prime.c | 36 ++++++++++++++++++++++++++++--------
 1 file changed, 28 insertions(+), 8 deletions(-)

diff --git a/math/ec-prime.c b/math/ec-prime.c
index c2ec2889..8a110375 100644
--- 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$% */
-- 
2.11.0