chiark - git - mdw - catacomb/blob - math/mp-modexp.c

   1 /* -*-c-*-
   2  *
   3  * General-purpose modular exponentiation
   4  *
   5  * (c) 2006 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "mp.h"
  31 #include "mpbarrett.h"
  32 #include "mpmont.h"
  33
  34 /*----- Main code ---------------------------------------------------------*/
  35
  36 /* --- @mp_modexp@ --- *
  37  *
  38  * Arguments:   @mp *d@ = fake destination
  39  *              @mp *x@ = base of exponentiation
  40  *              @mp *e@ = exponent
  41  *              @mp *n@ = modulus (must be positive)
  42  *
  43  * Returns:     The value %$x^e \bmod n$%.
  44  */
  45
  46 mp *mp_modexp(mp *d, mp *x, mp *e, mp *n)
  47 {
  48   if (MP_ODDP(n)) {
  49     mpmont mm;
  50     mpmont_create(&mm, n);
  51     d = mpmont_exp(&mm, d, x, e);
  52     mpmont_destroy(&mm);
  53   } else {
  54     mpbarrett mb;
  55     mpbarrett_create(&mb, n);
  56     d = mpbarrett_exp(&mb, d, x, e);
  57     mpbarrett_destroy(&mb);
  58   }
  59   return (d);
  60 }
  61
  62 /*----- Test rig ----------------------------------------------------------*/
  63
  64 #ifdef TEST_RIG
  65
  66 static int tmodexp(dstr *v)
  67 {
  68   mp *a = *(mp **)v[0].buf;
  69   mp *b = *(mp **)v[1].buf;
  70   mp *m = *(mp **)v[2].buf;
  71   mp *r = *(mp **)v[3].buf;
  72   mp *mr;
  73   int ok = 1;
  74
  75   mr = mp_modexp(MP_NEW, a, b, m);
  76
  77   if (!MP_EQ(mr, r)) {
  78     fputs("\n*** modexp failed", stderr);
  79     fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
  80     fputs("\n e = ", stderr); mp_writefile(b, stderr, 10);
  81     fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
  82     fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
  83     fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
  84     fputc('\n', stderr);
  85     ok = 0;
  86   }
  87
  88   MP_DROP(m);
  89   MP_DROP(a);
  90   MP_DROP(b);
  91   MP_DROP(r);
  92   MP_DROP(mr);
  93   assert(mparena_count(MPARENA_GLOBAL) == 0);
  94   return ok;
  95 }
  96
  97 static test_chunk tests[] = {
  98   { "modexp", tmodexp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
  99   { 0, 0, { 0 } }
 100 };
 101
 102 int main(int argc, char *argv[])
 103 {
 104   sub_init();
 105   test_run(argc, argv, tests, SRCDIR "/t/mp");
 106   return (0);
 107 }
 108
 109 #endif
 110
 111 /*----- That's all, folks -------------------------------------------------*/