Home | History | Annotate | Download | only in libtommath 
      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 (at) 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  */
     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) && 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