Add cyclic group abstraction, with test code. Separate off exponentation

[u/mdw/catacomb] / mpmont-mexp.c

diff --git a/mpmont-mexp.c b/mpmont-mexp.c
index a3f3f4b..7589990 100644 (file)
--- a/mpmont-mexp.c
+++ b/mpmont-mexp.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpmont-mexp.c,v 1.7 2002/01/13 13:49:14 mdw Exp $
+ * $Id: mpmont-mexp.c,v 1.8 2004/04/01 12:50:09 mdw Exp $
  *
  * Multiple simultaneous exponentiations
  *
@@ -30,6 +30,13 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mpmont-mexp.c,v $
+ * Revision 1.8  2004/04/01 12:50:09  mdw
+ * Add cyclic group abstraction, with test code.  Separate off exponentation
+ * functions for better static linking.  Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly.  Add
+ * table of standard prime-field subgroups.  (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
  * Revision 1.7  2002/01/13 13:49:14  mdw
  * Make @const@-correct.
  *
@@ -70,7 +77,7 @@
  *
  * Arguments:  @mpmont *mm@ = pointer to Montgomery reduction context
  *             @mp *d@ = fake destination
- *             @mp_expfactor *f@ = pointer to array of factors
+ *             @const mp_expfactor *f@ = pointer to array of factors
  *             @size_t n@ = number of factors supplied
  *
  * Returns:    If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
@@ -82,26 +89,46 @@
  *             except that the %$g_i$% and result are in Montgomery form.
  */
 
-mp *mpmont_mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
+static mp *mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
 {
-  mp *a = mp_copy(mm->r);
-  mp *spare;
+  mp *a = MP_COPY(mm->r);
+  mp *spare = MP_NEW;
+  mp *g = MP_NEW;
   size_t i;
 
-  spare = MP_NEW;
   for (i = 0; i < n; i++) {
-    if (f[i].exp->f & MP_BURN) {
+    mp *t;
+    if (f[i].exp->f & MP_BURN)
       spare = MP_NEWSEC;
-      break;
+    if (f[i].exp->f & MP_NEG) {
+      t = mpmont_reduce(mm, f[i].base, f[i].base);
+      mp_gcd(&g, 0, &t, mm->m, t);
+      assert(MP_EQ(g, MP_ONE));
+      f[i].base = mpmont_mul(mm, t, t, mm->r2);
     }
   }
-
+  mp_drop(g);
   EXP_SIMUL(a, f, n);
   mp_drop(d);
   mp_drop(spare);
+  for (i = 0; i < n; i++)
+    MP_DROP(f[i].base);
+  xfree(f);
   return (a);
 }
 
+mp *mpmont_mexpr(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
+{
+  mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
+  size_t i;
+
+  for (i = 0; i < n; i++) {
+    ff[i].base = MP_COPY(f[i].base);
+    ff[i].exp = f[i].exp;
+  }
+  return (mexpr(mm, d, ff, n));
+}
+
 /* --- @mpmont_mexp@ --- *
  *
  * Arguments:  @mpmont *mm@ = pointer to Montgomery reduction context
@@ -116,19 +143,15 @@ mp *mpmont_mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
 
 mp *mpmont_mexp(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
 {
-  mp_expfactor *v = xmalloc(sizeof(*v) * n);
+  mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
   size_t i;
 
   for (i = 0; i < n; i++) {
-    v[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
-    v[i].exp = f[i].exp;
+    ff[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
+    ff[i].exp = f[i].exp;
   }
-  d = mpmont_mexpr(mm, d, v, n);
-  for (i = 0; i < n; i++)
-    MP_DROP(v[i].base);
-  xfree(v);
-  d = mpmont_reduce(mm, d, d);
-  return (d);
+  d = mexpr(mm, d, ff, n);
+  return (mpmont_reduce(mm, d, d));
 }
 
 /*----- Test rig ----------------------------------------------------------*/