3 * $Id: mpmont.h,v 1.1 1999/11/17 18:02:16 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.1 1999/11/17 18:02:16 mdw
34 * New multiprecision integer arithmetic suite.
45 /*----- Header files ------------------------------------------------------*/
51 /*----- What's going on here? ---------------------------------------------*
53 * Given a little bit of precomputation, Montgomery reduction enables modular
54 * reductions of products to be calculated rather rapidly, without recourse
55 * to annoying things like division.
57 * Before starting, you need to do a little work. In particular, the
58 * following things need to be worked out:
60 * * %$m$%, which is the modulus you'll be working with.
62 * * %$b$%, the radix of the number system you're in (here, it's
65 * * %$-m^{-1} \bmod b$%, a useful number for the reduction step. (This
66 * means that the modulus mustn't be even. This shouldn't be a problem.)
68 * * %$R = b^n > m > b^{n - 1}$%, or at least %$\log_2 R$%.
70 * * %$R \bmod m$% and %$R^2 \bmod m$%, which are useful when doing
71 * calculations such as exponentiation.
73 * The result of a Montgomery reduction of %$x$% is %$x R^{-1} \bmod m$%,
74 * which doesn't look ever-so useful. The trick is to initially apply a
75 * factor of %$R$% to all of your numbers so that when you multiply and
76 * perform a Montgomery reduction you get %$(xR \cdot yR)R^{-1} \bmod m$%,
77 * which is just %$xyR \bmod m$%. Thanks to distributivity, even additions
78 * and subtractions can be performed on numbers in this form -- the extra
79 * factor of %$R$% just runs through all the calculations until it's finally
80 * stripped out by a final reduction operation.
83 /*----- Data structures ---------------------------------------------------*/
85 /* --- A Montgomery reduction context --- */
87 typedef struct mpmont
{
89 mpw mi
; /* %$-m^{-1} \bmod b$% */
90 size_t shift
; /* %$\log_2 R$% */
91 mp
*r
, *r2
; /* %$R \bmod m$%, %$R^2 \bmod m$% */
94 /*----- Functions provided ------------------------------------------------*/
96 /* --- @mpmont_create@ --- *
98 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
99 * @mp *m@ = modulus to use
103 * Use: Initializes a Montgomery reduction context ready for use.
106 extern void mpmont_create(mpmont */
*mm*/
, mp */
*m*/
);
108 /*----- That's all, folks -------------------------------------------------*/