5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 #ifndef CATACOMB_MPMONT_H
29 #define CATACOMB_MPMONT_H
35 /*----- Header files ------------------------------------------------------*/
41 /*----- Notes on Montgomery reduction -------------------------------------*
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.
47 * Before starting, you need to do a little work. In particular, the
48 * following things need to be worked out:
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.
54 * * %$b$%, the radix of the number system you're in (here, it's
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.)
60 * * %$R = b^n > m > b^{n - 1}$%, or at least %$\log_2 R$%.
62 * * %$R \bmod m$% and %$R^2 \bmod m$%, which are useful when doing
63 * calculations such as exponentiation.
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.
75 /*----- Data structures ---------------------------------------------------*/
77 /* --- A Montgomery reduction context --- */
79 typedef struct mpmont {
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$% */
86 /*----- Functions provided ------------------------------------------------*/
88 /* --- @mpmont_create@ --- *
90 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
91 * @mp *m@ = modulus to use
93 * Returns: Zero on success, nonzero on error.
95 * Use: Initializes a Montgomery reduction context ready for use.
96 * The argument @m@ must be a positive odd integer.
99 extern int mpmont_create(mpmont */*mm*/, mp */*m*/);
101 /* --- @mpmont_destroy@ --- *
103 * Arguments: @mpmont *mm@ = pointer to a Montgomery reduction context
107 * Use: Disposes of a context when it's no longer of any use to
111 extern void mpmont_destroy(mpmont */*mm*/);
113 /* --- @mpmont_reduce@ --- *
115 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
116 * @mp *d@ = destination
117 * @mp *a@ = source, assumed positive
119 * Returns: Result, %$a R^{-1} \bmod m$%.
122 extern mp *mpmont_reduce(mpmont */*mm*/, mp */*d*/, mp */*a*/);
124 /* --- @mpmont_mul@ --- *
126 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
127 * @mp *d@ = destination
128 * @mp *a, *b@ = sources, assumed positive
130 * Returns: Result, %$a b R^{-1} \bmod m$%.
133 extern mp *mpmont_mul(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*b*/);
135 /* --- @mpmont_expr@ --- *
137 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
138 * @mp *d@ = fake destination
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.
146 extern mp *mpmont_expr(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/);
148 /* --- @mpmont_exp@ --- *
150 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
151 * @mp *d@ = fake destination
155 * Returns: Result, %$a^e \bmod m$%.
158 extern mp *mpmont_exp(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/);
160 /* --- @mpmont_mexpr@ --- *
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
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
171 * %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
174 * except that the %$g_i$% and result are in Montgomery form.
177 extern mp *mpmont_mexpr(mpmont */*mm*/, mp */*d*/,
178 const mp_expfactor */*f*/, size_t /*n*/);
180 /* --- @mpmont_mexp@ --- *
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
187 * Returns: Product of bases raised to exponents, all mod @m@.
189 * Use: Convenient interface over @mpmont_mexpr@.
192 extern mp *mpmont_mexp(mpmont */*mm*/, mp */*d*/,
193 const mp_expfactor */*f*/, size_t /*n*/);
195 /*----- That's all, folks -------------------------------------------------*/