From 79a340293970d5f9b9c000f82769179f9ba551bd Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Sun, 21 Nov 1999 11:35:10 +0000
Subject: [PATCH] Performance improvement: use @mp_sqr@ and @mpmont_reduce@
 instead of @mpmont_mul@ for squaring in exponentiation.

---
 mpmont-mexp.c |  9 ++++++--
 mpmont.c      | 71 ++++++++++++++++++++++++++++++++---------------------------
 2 files changed, 46 insertions(+), 34 deletions(-)

diff --git a/mpmont-mexp.c b/mpmont-mexp.c
index 4180fbc..1d1266f 100644
--- a/mpmont-mexp.c
+++ b/mpmont-mexp.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpmont-mexp.c,v 1.1 1999/11/19 13:19:29 mdw Exp $
+ * $Id: mpmont-mexp.c,v 1.2 1999/11/21 11:35:10 mdw Exp $
  *
  * Multiplle simultaneous exponentiations
  *
@@ -30,6 +30,10 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mpmont-mexp.c,v $
+ * Revision 1.2  1999/11/21 11:35:10  mdw
+ * Performance improvement: use @mp_sqr@ and @mpmont_reduce@ instead of
+ * @mpmont_mul@ for squaring in exponentiation.
+ *
  * Revision 1.1  1999/11/19 13:19:29  mdw
  * Simultaneous exponentiation support.
  *
@@ -157,7 +161,8 @@ mp *mpmont_mexpr(mpmont *mm, mpmont_factor *f, size_t n)
     /* --- Accumulate the result --- */
 
     if (spare) {
-      dd = mpmont_mul(mm, spare, a, a);
+      dd = mp_sqr(spare, a);
+      dd = mpmont_reduce(mm, dd, dd);
       spare = a;
       a = dd;
     }
diff --git a/mpmont.c b/mpmont.c
index 4885151..66b7657 100644
--- a/mpmont.c
+++ b/mpmont.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpmont.c,v 1.2 1999/11/19 13:17:26 mdw Exp $
+ * $Id: mpmont.c,v 1.3 1999/11/21 11:35:10 mdw Exp $
  *
  * Montgomery reduction
  *
@@ -30,6 +30,10 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mpmont.c,v $
+ * Revision 1.3  1999/11/21 11:35:10  mdw
+ * Performance improvement: use @mp_sqr@ and @mpmont_reduce@ instead of
+ * @mpmont_mul@ for squaring in exponentiation.
+ *
  * Revision 1.2  1999/11/19 13:17:26  mdw
  * Add extra interface to exponentiation which returns a Montgomerized
  * result.
@@ -138,9 +142,9 @@ mp *mpmont_reduce(mpmont *mm, mp *d, const mp *a)
   n = MP_LEN(mm->m);
 
   if (d == a)
-    MP_MODIFY(d, 2 * n);
+    MP_MODIFY(d, 2 * n + 1);
   else {
-    MP_MODIFY(d, 2 * n);
+    MP_MODIFY(d, 2 * n + 1);
     memcpy(d->v, a->v, MPWS(MP_LEN(a)));
     memset(d->v + MP_LEN(a), 0, MPWS(MP_LEN(d) - MP_LEN(a)));
   }
@@ -256,7 +260,8 @@ mp *mpmont_expr(mpmont *mm, const mp *a, const mp *e)
       mp *dd;
       if (MP_BIT(&sc)) {
 	while (sq) {
-	  dd = mpmont_mul(mm, spare, ar, ar);	  
+	  dd = mp_sqr(spare, ar);
+	  dd = mpmont_reduce(mm, dd, dd);
 	  spare = ar; ar = dd;
 	  sq--;
 	}
@@ -346,51 +351,53 @@ static int tmul(dstr *v)
   mp *a = *(mp **)v[1].buf;
   mp *b = *(mp **)v[2].buf;
   mp *r = *(mp **)v[3].buf;
-  mp *mr, *qr;
   int ok = 1;
 
   mpmont mm;
   mpmont_create(&mm, m);
 
   {
+    mp *qr = mp_mul(MP_NEW, a, b);
+    mp_div(0, &qr, qr, m);
+
+    if (MP_CMP(qr, !=, r)) {
+      fputs("\n*** classical modmul failed", stderr);
+      fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+      fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+      fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
+      fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+      fputs("\nqr = ", stderr); mp_writefile(qr, stderr, 10);
+      fputc('\n', stderr);
+      ok = 0;
+    }
+
+    mp_drop(qr);
+  }
+
+  {
     mp *ar = mpmont_mul(&mm, MP_NEW, a, mm.r2);
     mp *br = mpmont_mul(&mm, MP_NEW, b, mm.r2);
-    mr = mpmont_mul(&mm, MP_NEW, ar, br);
+    mp *mr = mpmont_mul(&mm, MP_NEW, ar, br);
     mr = mpmont_reduce(&mm, mr, mr);
+    if (MP_CMP(mr, !=, r)) {
+      fputs("\n*** montgomery modmul failed", stderr);
+      fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+      fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+      fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
+      fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+      fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
+      fputc('\n', stderr);
+      ok = 0;
+    }
     MP_DROP(ar); MP_DROP(br);
+    mp_drop(mr);
   }
 
-  qr = mp_mul(MP_NEW, a, b);
-  mp_div(0, &qr, qr, m);
-
-  if (MP_CMP(qr, !=, r)) {
-    fputs("\n*** classical modmul failed", stderr);
-    fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
-    fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
-    fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
-    fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
-    fputs("\nqr = ", stderr); mp_writefile(qr, stderr, 10);
-    fputc('\n', stderr);
-    ok = 0;
-  }
-
-  if (MP_CMP(mr, !=, r)) {
-    fputs("\n*** montgomery modmul failed", stderr);
-    fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
-    fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
-    fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
-    fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
-    fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
-    fputc('\n', stderr);
-    ok = 0;
-  }
 
   MP_DROP(m);
   MP_DROP(a);
   MP_DROP(b);
   MP_DROP(r);
-  MP_DROP(mr);
-  MP_DROP(qr);
   mpmont_destroy(&mm);
   return ok;
 }
-- 
2.11.0