3 * $Id: mpmont.h,v 1.7 2004/04/01 12:50:09 mdw Exp $
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.7 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.)
40 * Revision 1.6 2002/01/13 13:49:25 mdw
41 * Make @const@-correct.
43 * Revision 1.5 2001/06/16 13:00:04 mdw
44 * Moved @mpmont_factor@ to <mp.h>. Documented interface change to
45 * @mpmont_expr@ and @mpmont_mexpr@ -- the arguments are now in Montgomery
48 * Revision 1.4 1999/12/11 01:51:14 mdw
49 * Use a Karatsuba-based reduction for large moduli.
51 * Revision 1.3 1999/12/10 23:29:48 mdw
52 * Change header file guard names.
54 * Revision 1.2 1999/11/19 13:17:43 mdw
55 * Add extra interface to exponentiation which returns a Montgomerized
56 * result. Add simultaneous exponentiation interface.
58 * Revision 1.1 1999/11/17 18:02:16 mdw
59 * New multiprecision integer arithmetic suite.
63 #ifndef CATACOMB_MPMONT_H
64 #define CATACOMB_MPMONT_H
70 /*----- Header files ------------------------------------------------------*/
76 /*----- Notes on Montgomery reduction -------------------------------------*
78 * Given a little bit of precomputation, Montgomery reduction enables modular
79 * reductions of products to be calculated rather rapidly, without recourse
80 * to annoying things like division.
82 * Before starting, you need to do a little work. In particular, the
83 * following things need to be worked out:
85 * * %$m$%, which is the modulus you'll be working with. This must be odd,
86 * otherwise the whole thing doesn't work. You're better off using
87 * Barrett reduction if your modulus might be even.
89 * * %$b$%, the radix of the number system you're in (here, it's
92 * * %$-m^{-1} \bmod b$%, a useful number for the reduction step. (This
93 * means that the modulus mustn't be even. This shouldn't be a problem.)
95 * * %$R = b^n > m > b^{n - 1}$%, or at least %$\log_2 R$%.
97 * * %$R \bmod m$% and %$R^2 \bmod m$%, which are useful when doing
98 * calculations such as exponentiation.
100 * The result of a Montgomery reduction of %$x$% is %$x R^{-1} \bmod m$%,
101 * which doesn't look ever-so useful. The trick is to initially apply a
102 * factor of %$R$% to all of your numbers so that when you multiply and
103 * perform a Montgomery reduction you get %$(x R \cdot y R) R^{-1} \bmod m$%,
104 * which is just %$x y R \bmod m$%. Thanks to distributivity, even additions
105 * and subtractions can be performed on numbers in this form -- the extra
106 * factor of %$R$% just runs through all the calculations until it's finally
107 * stripped out by a final reduction operation.
110 /*----- Data structures ---------------------------------------------------*/
112 /* --- A Montgomery reduction context --- */
114 typedef struct mpmont
{
116 mp
*mi
; /* %$-m^{-1} \bmod R$% */
117 size_t n
; /* %$\log_b R$% */
118 mp
*r
, *r2
; /* %$R \bmod m$%, %$R^2 \bmod m$% */
121 /*----- Functions provided ------------------------------------------------*/
123 /* --- @mpmont_create@ --- *
125 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
126 * @mp *m@ = modulus to use
130 * Use: Initializes a Montgomery reduction context ready for use.
131 * The argument @m@ must be a positive odd integer.
134 extern void mpmont_create(mpmont */
*mm*/
, mp */
*m*/
);
136 /* --- @mpmont_destroy@ --- *
138 * Arguments: @mpmont *mm@ = pointer to a Montgomery reduction context
142 * Use: Disposes of a context when it's no longer of any use to
146 extern void mpmont_destroy(mpmont */
*mm*/
);
148 /* --- @mpmont_reduce@ --- *
150 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
151 * @mp *d@ = destination
152 * @mp *a@ = source, assumed positive
154 * Returns: Result, %$a R^{-1} \bmod m$%.
157 extern mp
*mpmont_reduce(mpmont */
*mm*/
, mp */
*d*/
, mp */
*a*/
);
159 /* --- @mpmont_mul@ --- *
161 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
162 * @mp *d@ = destination
163 * @mp *a, *b@ = sources, assumed positive
165 * Returns: Result, %$a b R^{-1} \bmod m$%.
168 extern mp
*mpmont_mul(mpmont */
*mm*/
, mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
170 /* --- @mpmont_expr@ --- *
172 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
173 * @mp *d@ = fake destination
177 * Returns: Result, %$(a R^{-1})^e R \bmod m$%. This is useful if
178 * further modular arithmetic is to be performed on the result.
181 extern mp
*mpmont_expr(mpmont */
*mm*/
, mp */
*d*/
, mp */
*a*/
, mp */
*e*/
);
183 /* --- @mpmont_exp@ --- *
185 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
186 * @mp *d@ = fake destination
190 * Returns: Result, %$a^e \bmod m$%.
193 extern mp
*mpmont_exp(mpmont */
*mm*/
, mp */
*d*/
, mp */
*a*/
, mp */
*e*/
);
195 /* --- @mpmont_mexpr@ --- *
197 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
198 * @mp *d@ = fake destination
199 * @const mp_expfactor *f@ = pointer to array of factors
200 * @size_t n@ = number of factors supplied
202 * Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
203 * exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
206 * %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
209 * except that the %$g_i$% and result are in Montgomery form.
212 extern mp
*mpmont_mexpr(mpmont */
*mm*/
, mp */
*d*/
,
213 const mp_expfactor */
*f*/
, size_t /*n*/);
215 /* --- @mpmont_mexp@ --- *
217 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
218 * @mp *d@ = fake destination
219 * @const mp_expfactor *f@ = pointer to array of factors
220 * @size_t n@ = number of factors supplied
222 * Returns: Product of bases raised to exponents, all mod @m@.
224 * Use: Convenient interface over @mpmont_mexpr@.
227 extern mp
*mpmont_mexp(mpmont */
*mm*/
, mp */
*d*/
,
228 const mp_expfactor */
*f*/
, size_t /*n*/);
230 /*----- That's all, folks -------------------------------------------------*/