1 /* -*-c-*-

2 *

3 * $Id: mpmont.h,v 1.1 1999/11/17 18:02:16 mdw Exp $

4 *

5 * Montgomery reduction

6 *

7 * (c) 1999 Straylight/Edgeware

8 */

10 /*----- Licensing notice --------------------------------------------------*

11 *

12 * This file is part of Catacomb.

13 *

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.

18 *

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.

23 *

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,

27 * MA 02111-1307, USA.

28 */

30 /*----- Revision history --------------------------------------------------*

31 *

32 * $Log: mpmont.h,v $

33 * Revision 1.1 1999/11/17 18:02:16 mdw

34 * New multiprecision integer arithmetic suite.

35 *

36 */

38 #ifndef MPMONT_H

39 #define MPMONT_H

41 #ifdef __cplusplus

43 #endif

45 /*----- Header files ------------------------------------------------------*/

47 #ifndef MP_H

49 #endif

51 /*----- What's going on here? ---------------------------------------------*

52 *

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.

56 *

57 * Before starting, you need to do a little work. In particular, the

58 * following things need to be worked out:

59 *

60 * * %$m$%, which is the modulus you'll be working with.

61 *

62 * * %$b$%, the radix of the number system you're in (here, it's

63 * @MPW_MAX + 1@).

64 *

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.)

67 *

68 * * %$R = b^n > m > b^{n - 1}$%, or at least %$\log_2 R$%.

69 *

70 * * %$R \bmod m$% and %$R^2 \bmod m$%, which are useful when doing

71 * calculations such as exponentiation.

72 *

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.

81 */

83 /*----- Data structures ---------------------------------------------------*/

85 /* --- A Montgomery reduction context --- */

94 /*----- Functions provided ------------------------------------------------*/

96 /* --- @mpmont_create@ --- *

97 *

98 * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context

99 * @mp *m@ = modulus to use

100 *

101 * Returns: ---

102 *

103 * Use: Initializes a Montgomery reduction context ready for use.

104 */

108 /*----- That's all, folks -------------------------------------------------*/

110 #ifdef __cplusplus

111 }

112 #endif

114 #endif