## Mercurial > dropbear

### annotate bn_mp_exptmod.c @ 282:91fbc376f010 libtommath-orig libtommath-0.35

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

Import of libtommath 0.35
From ltm-0.35.tar.bz2 SHA1 of 3f193dbae9351e92d02530994fa18236f7fde01c

author | Matt Johnston <matt@ucc.asn.au> |
---|---|

date | Wed, 08 Mar 2006 13:16:18 +0000 |

parents | |

children | 97db060d0ef5 |

rev | line source |
---|---|

282 | 1 #include <tommath.h> |

2 #ifdef BN_MP_EXPTMOD_C | |

3 /* LibTomMath, multiple-precision integer library -- Tom St Denis | |

4 * | |

5 * LibTomMath is a library that provides multiple-precision | |

6 * integer arithmetic as well as number theoretic functionality. | |

7 * | |

8 * The library was designed directly after the MPI library by | |

9 * Michael Fromberger but has been written from scratch with | |

10 * additional optimizations in place. | |

11 * | |

12 * The library is free for all purposes without any express | |

13 * guarantee it works. | |

14 * | |

15 * Tom St Denis, [email protected], http://math.libtomcrypt.org | |

16 */ | |

17 | |

18 | |

19 /* this is a shell function that calls either the normal or Montgomery | |

20 * exptmod functions. Originally the call to the montgomery code was | |

21 * embedded in the normal function but that wasted alot of stack space | |

22 * for nothing (since 99% of the time the Montgomery code would be called) | |

23 */ | |

24 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y) | |

25 { | |

26 int dr; | |

27 | |

28 /* modulus P must be positive */ | |

29 if (P->sign == MP_NEG) { | |

30 return MP_VAL; | |

31 } | |

32 | |

33 /* if exponent X is negative we have to recurse */ | |

34 if (X->sign == MP_NEG) { | |

35 #ifdef BN_MP_INVMOD_C | |

36 mp_int tmpG, tmpX; | |

37 int err; | |

38 | |

39 /* first compute 1/G mod P */ | |

40 if ((err = mp_init(&tmpG)) != MP_OKAY) { | |

41 return err; | |

42 } | |

43 if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) { | |

44 mp_clear(&tmpG); | |

45 return err; | |

46 } | |

47 | |

48 /* now get |X| */ | |

49 if ((err = mp_init(&tmpX)) != MP_OKAY) { | |

50 mp_clear(&tmpG); | |

51 return err; | |

52 } | |

53 if ((err = mp_abs(X, &tmpX)) != MP_OKAY) { | |

54 mp_clear_multi(&tmpG, &tmpX, NULL); | |

55 return err; | |

56 } | |

57 | |

58 /* and now compute (1/G)**|X| instead of G**X [X < 0] */ | |

59 err = mp_exptmod(&tmpG, &tmpX, P, Y); | |

60 mp_clear_multi(&tmpG, &tmpX, NULL); | |

61 return err; | |

62 #else | |

63 /* no invmod */ | |

64 return MP_VAL; | |

65 #endif | |

66 } | |

67 | |

68 /* modified diminished radix reduction */ | |

69 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) | |

70 if (mp_reduce_is_2k_l(P) == MP_YES) { | |

71 return s_mp_exptmod(G, X, P, Y, 1); | |

72 } | |

73 #endif | |

74 | |

75 #ifdef BN_MP_DR_IS_MODULUS_C | |

76 /* is it a DR modulus? */ | |

77 dr = mp_dr_is_modulus(P); | |

78 #else | |

79 /* default to no */ | |

80 dr = 0; | |

81 #endif | |

82 | |

83 #ifdef BN_MP_REDUCE_IS_2K_C | |

84 /* if not, is it a unrestricted DR modulus? */ | |

85 if (dr == 0) { | |

86 dr = mp_reduce_is_2k(P) << 1; | |

87 } | |

88 #endif | |

89 | |

90 /* if the modulus is odd or dr != 0 use the montgomery method */ | |

91 #ifdef BN_MP_EXPTMOD_FAST_C | |

92 if (mp_isodd (P) == 1 || dr != 0) { | |

93 return mp_exptmod_fast (G, X, P, Y, dr); | |

94 } else { | |

95 #endif | |

96 #ifdef BN_S_MP_EXPTMOD_C | |

97 /* otherwise use the generic Barrett reduction technique */ | |

98 return s_mp_exptmod (G, X, P, Y, 0); | |

99 #else | |

100 /* no exptmod for evens */ | |

101 return MP_VAL; | |

102 #endif | |

103 #ifdef BN_MP_EXPTMOD_FAST_C | |

104 } | |

105 #endif | |

106 } | |

107 | |

108 #endif |