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

[u/mdw/catacomb] / mpmont.c

diff --git a/mpmont.c b/mpmont.c
index c644801..926fde8 100644 (file)
--- a/mpmont.c
+++ b/mpmont.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpmont.c,v 1.16 2002/01/13 13:40:31 mdw Exp $
+ * $Id: mpmont.c,v 1.17 2004/04/01 12:50:09 mdw Exp $
  *
  * Montgomery reduction
  *
@@ -30,6 +30,13 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mpmont.c,v $
+ * Revision 1.17  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.16  2002/01/13 13:40:31  mdw
  * Avoid trashing arguments before we've used them.
  *
@@ -94,7 +101,6 @@
 
 #include "mp.h"
 #include "mpmont.h"
-#include "mpmont-exp.h"
 
 /*----- Tweakables --------------------------------------------------------*/
 
@@ -370,55 +376,6 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b)
 
 #endif
 
-/*----- Exponentiation ----------------------------------------------------*/
-
-/* --- @mpmont_expr@ --- *
- *
- * Arguments:  @mpmont *mm@ = pointer to Montgomery reduction context
- *             @mp *d@ = fake destination
- *             @mp *a@ = base
- *             @mp *e@ = exponent
- *
- * Returns:    Result, %$(a R^{-1})^e R \bmod m$%.
- */
-
-mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e)
-{
-  mp *x = MP_COPY(mm->r);
-  mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
-
-  MP_SHRINK(e);
-  if (MP_LEN(e) == 0)
-    ;
-  else if (MP_LEN(e) < EXP_THRESH)
-    EXP_SIMPLE(x, a, e);
-  else
-    EXP_WINDOW(x, a, e);
-  mp_drop(d);
-  mp_drop(spare);
-  return (x);
-}
-
-/* --- @mpmont_exp@ --- *
- *
- * Arguments:  @mpmont *mm@ = pointer to Montgomery reduction context
- *             @mp *d@ = fake destination
- *             @mp *a@ = base
- *             @mp *e@ = exponent
- *
- * Returns:    Result, %$a^e \bmod m$%.
- */
-
-mp *mpmont_exp(mpmont *mm, mp *d, mp *a, mp *e)
-{
-  e = MP_COPY(e);
-  d = mpmont_mul(mm, d, a, mm->r2);
-  d = mpmont_expr(mm, d, d, e);
-  d = mpmont_reduce(mm, d, d);
-  MP_DROP(e);
-  return (d);
-}
-
 /*----- Test rig ----------------------------------------------------------*/
 
 #ifdef TEST_RIG
@@ -528,46 +485,9 @@ static int tmul(dstr *v)
   return ok;
 }
 
-static int texp(dstr *v)
-{
-  mp *m = *(mp **)v[0].buf;
-  mp *a = *(mp **)v[1].buf;
-  mp *b = *(mp **)v[2].buf;
-  mp *r = *(mp **)v[3].buf;
-  mp *mr;
-  int ok = 1;
-
-  mpmont mm;
-  mpmont_create(&mm, m);
-
-  mr = mpmont_exp(&mm, MP_NEW, a, b);
-
-  if (!MP_EQ(mr, r)) {
-    fputs("\n*** montgomery modexp failed", stderr);
-    fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
-    fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
-    fputs("\n e = ", 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);
-  mpmont_destroy(&mm);
-  assert(mparena_count(MPARENA_GLOBAL) == 0);
-  return ok;
-}
-
-
 static test_chunk tests[] = {
   { "create", tcreate, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
   { "mul", tmul, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
-  { "exp", texp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
   { 0, 0, { 0 } },
 };