chiark / gitweb /
rand/rand.c (rand_gate): Evolve r->ibits in a more sensible manner.
[catacomb] / 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 -------------------------------------------------*/