chiark - git - mdw - catacomb/blob - mpbarrett-mexp.c

   1 /* -*-c-*-
   2  *
   3  * $Id: mpbarrett-mexp.c,v 1.2 2004/04/01 12:50:09 mdw Exp $
   4  *
   5  * Multiple simultaneous exponentiations
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mpbarrett-mexp.c,v $
  33  * Revision 1.2  2004/04/01 12:50:09  mdw
  34  * Add cyclic group abstraction, with test code.  Separate off exponentation
  35  * functions for better static linking.  Fix a buttload of bugs on the way.
  36  * Generally ensure that negative exponents do inversion correctly.  Add
  37  * table of standard prime-field subgroups.  (Binary field subgroups are
  38  * currently unimplemented but easy to add if anyone ever finds a good one.)
  39  *
  40  * Revision 1.1  2001/06/16 12:58:34  mdw
  41  * Added simultaneous exponentiation with Barrett reduction.
  42  *
  43  */
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #include "mp.h"
  48 #include "mpbarrett.h"
  49
  50 #define EXP_WINSZ 3
  51 #include "mpbarrett-exp.h"
  52
  53 /*----- Main code ---------------------------------------------------------*/
  54
  55 /* --- @mpbarrett_mexp@ --- *
  56  *
  57  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
  58  *              @mp *d@ = fake destination
  59  *              @const mp_expfactor *f@ = pointer to array of factors
  60  *              @size_t n@ = number of factors supplied
  61  *
  62  * Returns:     If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
  63  *              exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
  64  *              is:
  65  *
  66  *              %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
  67  */
  68
  69 mp *mpbarrett_mexp(mpbarrett *mb, mp *d, const mp_expfactor *f, size_t n)
  70 {
  71   mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
  72   mp *a = MP_ONE;
  73   mp *spare;
  74   mp *g = MP_NEW;
  75   size_t i;
  76
  77   spare = MP_NEW;
  78   for (i = 0; i < n; i++) {
  79     if (f[i].exp->f & MP_BURN)
  80       spare = MP_NEWSEC;
  81     if (!(f[i].exp->f & MP_NEG))
  82       ff[i].base = MP_COPY(f[i].base);
  83     else {
  84       ff[i].base = MP_NEW;
  85       mp_gcd(&g, 0, &ff[i].base, mb->m, f[i].base);
  86       assert(MP_EQ(g, MP_ONE));
  87     }
  88     ff[i].exp = f[i].exp;
  89   }
  90   mp_drop(g);
  91   EXP_SIMUL(a, ff, n);
  92   mp_drop(d);
  93   mp_drop(spare);
  94   for (i = 0; i < n; i++)
  95     mp_drop(ff[i].base);
  96   xfree(ff);
  97   return (a);
  98 }
  99
 100 /*----- Test rig ----------------------------------------------------------*/
 101
 102 #ifdef TEST_RIG
 103
 104 #include <mLib/testrig.h>
 105
 106 static int verify(size_t n, dstr *v)
 107 {
 108   mp *m = *(mp **)v[0].buf;
 109   mp_expfactor *f = xmalloc(n * sizeof(*f));
 110   mp *r, *rr;
 111   size_t i, j;
 112   mpbarrett mb;
 113   int ok = 1;
 114
 115   j = 1;
 116   for (i = 0; i < n; i++) {
 117     f[i].base = *(mp **)v[j++].buf;
 118     f[i].exp = *(mp **)v[j++].buf;
 119   }
 120
 121   rr = *(mp **)v[j].buf;
 122   mpbarrett_create(&mb, m);
 123   r = mpbarrett_mexp(&mb, MP_NEW, f, n);
 124   if (!MP_EQ(r, rr)) {
 125     fputs("\n*** mexp failed\n", stderr);
 126     fputs("m = ", stderr); mp_writefile(m, stderr, 10);
 127     for (i = 0; i < n; i++) {
 128       fprintf(stderr, "\ng_%u = ", i);
 129       mp_writefile(f[i].base, stderr, 10);
 130       fprintf(stderr, "\ne_%u = ", i);
 131       mp_writefile(f[i].exp, stderr, 10);
 132     }
 133     fputs("\nr = ", stderr); mp_writefile(r, stderr, 10);
 134     fputs("\nR = ", stderr); mp_writefile(rr, stderr, 10);
 135     fputc('\n', stderr);
 136     ok = 0;
 137   }
 138
 139   for (i = 0; i < n; i++) {
 140     MP_DROP(f[i].base);
 141     MP_DROP(f[i].exp);
 142   }
 143   MP_DROP(m);
 144   MP_DROP(r);
 145   MP_DROP(rr);
 146   mpbarrett_destroy(&mb);
 147   assert(mparena_count(MPARENA_GLOBAL) == 0);
 148   return (ok);
 149 }
 150
 151 static int t1(dstr *v) { return verify(1, v); }
 152 static int t2(dstr *v) { return verify(2, v); }
 153 static int t3(dstr *v) { return verify(3, v); }
 154 static int t4(dstr *v) { return verify(4, v); }
 155 static int t5(dstr *v) { return verify(5, v); }
 156
 157 static test_chunk tests[] = {
 158   { "mexp-1", t1, { &type_mp,
 159                     &type_mp, &type_mp,
 160                     &type_mp, 0 } },
 161   { "mexp-2", t2, { &type_mp,
 162                     &type_mp, &type_mp,
 163                     &type_mp, &type_mp,
 164                     &type_mp, 0 } },
 165   { "mexp-3", t3, { &type_mp,
 166                     &type_mp, &type_mp,
 167                     &type_mp, &type_mp,
 168                     &type_mp, &type_mp,
 169                     &type_mp, 0 } },
 170   { "mexp-4", t4, { &type_mp,
 171                     &type_mp, &type_mp,
 172                     &type_mp, &type_mp,
 173                     &type_mp, &type_mp,
 174                     &type_mp, &type_mp,
 175                     &type_mp, 0 } },
 176   { "mexp-5", t5, { &type_mp,
 177                     &type_mp, &type_mp,
 178                     &type_mp, &type_mp,
 179                     &type_mp, &type_mp,
 180                     &type_mp, &type_mp,
 181                     &type_mp, &type_mp,
 182                     &type_mp, 0 } },
 183   { 0, 0, { 0 } }
 184 };
 185
 186 int main(int argc, char *argv[])
 187 {
 188   sub_init();
 189   test_run(argc, argv, tests, SRCDIR "/tests/mpbarrett");
 190   return (0);
 191 }
 192
 193 #endif
 194
 195 /*----- That's all, folks -------------------------------------------------*/