chiark / gitweb /
configure.ac, Makefile.am: Collect libs only needed by Catcomb itself.
[catacomb] / math / mpmont.h
1 /* -*-c-*-
2  *
3  * Montgomery reduction
4  *
5  * (c) 1999 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 #ifndef CATACOMB_MPMONT_H
29 #define CATACOMB_MPMONT_H
30
31 #ifdef __cplusplus
32   extern "C" {
33 #endif
34
35 /*----- Header files ------------------------------------------------------*/
36
37 #ifndef CATACOMB_MP_H
38 #  include "mp.h"
39 #endif
40
41 /*----- Notes on Montgomery reduction -------------------------------------*
42  *
43  * Given a little bit of precomputation, Montgomery reduction enables modular
44  * reductions of products to be calculated rather rapidly, without recourse
45  * to annoying things like division.
46  *
47  * Before starting, you need to do a little work.  In particular, the
48  * following things need to be worked out:
49  *
50  *   * %$m$%, which is the modulus you'll be working with.  This must be odd,
51  *     otherwise the whole thing doesn't work.  You're better off using
52  *     Barrett reduction if your modulus might be even.
53  *
54  *   * %$b$%, the radix of the number system you're in (here, it's
55  *     @MPW_MAX + 1@).
56  *
57  *   * %$-m^{-1} \bmod b$%, a useful number for the reduction step.  (This
58  *     means that the modulus mustn't be even.  This shouldn't be a problem.)
59  *
60  *   * %$R = b^n > m > b^{n - 1}$%, or at least %$\log_2 R$%.
61  *
62  *   * %$R \bmod m$% and %$R^2 \bmod m$%, which are useful when doing
63  *     calculations such as exponentiation.
64  *
65  * The result of a Montgomery reduction of %$x$% is %$x R^{-1} \bmod m$%,
66  * which doesn't look ever-so useful.  The trick is to initially apply a
67  * factor of %$R$% to all of your numbers so that when you multiply and
68  * perform a Montgomery reduction you get %$(x R \cdot y R) R^{-1} \bmod m$%,
69  * which is just %$x y R \bmod m$%.  Thanks to distributivity, even additions
70  * and subtractions can be performed on numbers in this form -- the extra
71  * factor of %$R$% just runs through all the calculations until it's finally
72  * stripped out by a final reduction operation.
73  */
74
75 /*----- Data structures ---------------------------------------------------*/
76
77 /* --- A Montgomery reduction context --- */
78
79 typedef struct mpmont {
80   mp *m;                                /* Modulus */
81   mp *mi;                               /* %$-m^{-1} \bmod R$% */
82   size_t n;                             /* %$\log_b R$% */
83   mp *r, *r2;                           /* %$R \bmod m$%, %$R^2 \bmod m$% */
84 } mpmont;
85
86 /*----- Functions provided ------------------------------------------------*/
87
88 /* --- @mpmont_create@ --- *
89  *
90  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
91  *              @mp *m@ = modulus to use
92  *
93  * Returns:     Zero on success, nonzero on error.
94  *
95  * Use:         Initializes a Montgomery reduction context ready for use.
96  *              The argument @m@ must be a positive odd integer.
97  */
98
99 extern int mpmont_create(mpmont */*mm*/, mp */*m*/);
100
101 /* --- @mpmont_destroy@ --- *
102  *
103  * Arguments:   @mpmont *mm@ = pointer to a Montgomery reduction context
104  *
105  * Returns:     ---
106  *
107  * Use:         Disposes of a context when it's no longer of any use to
108  *              anyone.
109  */
110
111 extern void mpmont_destroy(mpmont */*mm*/);
112
113 /* --- @mpmont_reduce@ --- *
114  *
115  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
116  *              @mp *d@ = destination
117  *              @mp *a@ = source, assumed positive
118  *
119  * Returns:     Result, %$a R^{-1} \bmod m$%.
120  */
121
122 extern mp *mpmont_reduce(mpmont */*mm*/, mp */*d*/, mp */*a*/);
123
124 /* --- @mpmont_mul@ --- *
125  *
126  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
127  *              @mp *d@ = destination
128  *              @mp *a, *b@ = sources, assumed positive
129  *
130  * Returns:     Result, %$a b R^{-1} \bmod m$%.
131  */
132
133 extern mp *mpmont_mul(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*b*/);
134
135 /* --- @mpmont_expr@ --- *
136  *
137  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
138  *              @mp *d@ = fake destination
139  *              @mp *a@ = base
140  *              @mp *e@ = exponent
141  *
142  * Returns:     Result, %$(a R^{-1})^e R \bmod m$%.  This is useful if
143  *              further modular arithmetic is to be performed on the result.
144  */
145
146 extern mp *mpmont_expr(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/);
147
148 /* --- @mpmont_exp@ --- *
149  *
150  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
151  *              @mp *d@ = fake destination
152  *              @mp *a@ = base
153  *              @mp *e@ = exponent
154  *
155  * Returns:     Result, %$a^e \bmod m$%.
156  */
157
158 extern mp *mpmont_exp(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/);
159
160 /* --- @mpmont_mexpr@ --- *
161  *
162  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
163  *              @mp *d@ = fake destination
164  *              @const mp_expfactor *f@ = pointer to array of factors
165  *              @size_t n@ = number of factors supplied
166  *
167  * Returns:     If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
168  *              exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
169  *              is:
170  *
171  *              %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
172  *
173  *
174  *              except that the %$g_i$% and result are in Montgomery form.
175  */
176
177 extern mp *mpmont_mexpr(mpmont */*mm*/, mp */*d*/,
178                         const mp_expfactor */*f*/, size_t /*n*/);
179
180 /* --- @mpmont_mexp@ --- *
181  *
182  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
183  *              @mp *d@ = fake destination
184  *              @const mp_expfactor *f@ = pointer to array of factors
185  *              @size_t n@ = number of factors supplied
186  *
187  * Returns:     Product of bases raised to exponents, all mod @m@.
188  *
189  * Use:         Convenient interface over @mpmont_mexpr@.
190  */
191
192 extern mp *mpmont_mexp(mpmont */*mm*/, mp */*d*/,
193                        const mp_expfactor */*f*/, size_t /*n*/);
194
195 /*----- That's all, folks -------------------------------------------------*/
196
197 #ifdef __cplusplus
198   }
199 #endif
200
201 #endif