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, tomstdenis@gmail.com, http://math.libtomcrypt.com 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 */ 24int 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) && defined(BN_S_MP_EXPTMOD_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 109 110/* $Source: /cvs/libtom/libtommath/bn_mp_exptmod.c,v $ */ 111/* $Revision: 1.4 $ */ 112/* $Date: 2006/03/31 14:18:44 $ */ 113