Home | History | Annotate | Line # | Download | only in libtommath 
      1 /*	$NetBSD: bn_mp_exptmod.c,v 1.2 2017/01/28 21:31:47 christos Exp $	*/
      2 
      3 #include <tommath.h>
      4 #ifdef BN_MP_EXPTMOD_C
      5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
      6  *
      7  * LibTomMath is a library that provides multiple-precision
      8  * integer arithmetic as well as number theoretic functionality.
      9  *
     10  * The library was designed directly after the MPI library by
     11  * Michael Fromberger but has been written from scratch with
     12  * additional optimizations in place.
     13  *
     14  * The library is free for all purposes without any express
     15  * guarantee it works.
     16  *
     17  * Tom St Denis, tomstdenis (at) gmail.com, http://libtom.org
     18  */
     19 
     20 
     21 /* this is a shell function that calls either the normal or Montgomery
     22  * exptmod functions.  Originally the call to the montgomery code was
     23  * embedded in the normal function but that wasted alot of stack space
     24  * for nothing (since 99% of the time the Montgomery code would be called)
     25  */
     26 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
     27 {
     28   int dr;
     29 
     30   /* modulus P must be positive */
     31   if (P->sign == MP_NEG) {
     32      return MP_VAL;
     33   }
     34 
     35   /* if exponent X is negative we have to recurse */
     36   if (X->sign == MP_NEG) {
     37 #ifdef BN_MP_INVMOD_C
     38      mp_int tmpG, tmpX;
     39      int err;
     40 
     41      /* first compute 1/G mod P */
     42      if ((err = mp_init(&tmpG)) != MP_OKAY) {
     43         return err;
     44      }
     45      if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
     46         mp_clear(&tmpG);
     47         return err;
     48      }
     49 
     50      /* now get |X| */
     51      if ((err = mp_init(&tmpX)) != MP_OKAY) {
     52         mp_clear(&tmpG);
     53         return err;
     54      }
     55      if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
     56         mp_clear_multi(&tmpG, &tmpX, NULL);
     57         return err;
     58      }
     59 
     60      /* and now compute (1/G)**|X| instead of G**X [X < 0] */
     61      err = mp_exptmod(&tmpG, &tmpX, P, Y);
     62      mp_clear_multi(&tmpG, &tmpX, NULL);
     63      return err;
     64 #else
     65      /* no invmod */
     66      return MP_VAL;
     67 #endif
     68   }
     69 
     70 /* modified diminished radix reduction */
     71 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C)
     72   if (mp_reduce_is_2k_l(P) == MP_YES) {
     73      return s_mp_exptmod(G, X, P, Y, 1);
     74   }
     75 #endif
     76 
     77 #ifdef BN_MP_DR_IS_MODULUS_C
     78   /* is it a DR modulus? */
     79   dr = mp_dr_is_modulus(P);
     80 #else
     81   /* default to no */
     82   dr = 0;
     83 #endif
     84 
     85 #ifdef BN_MP_REDUCE_IS_2K_C
     86   /* if not, is it a unrestricted DR modulus? */
     87   if (dr == 0) {
     88      dr = mp_reduce_is_2k(P) << 1;
     89   }
     90 #endif
     91 
     92   /* if the modulus is odd or dr != 0 use the montgomery method */
     93 #ifdef BN_MP_EXPTMOD_FAST_C
     94   if (mp_isodd (P) == 1 || dr !=  0) {
     95     return mp_exptmod_fast (G, X, P, Y, dr);
     96   } else {
     97 #endif
     98 #ifdef BN_S_MP_EXPTMOD_C
     99     /* otherwise use the generic Barrett reduction technique */
    100     return s_mp_exptmod (G, X, P, Y, 0);
    101 #else
    102     /* no exptmod for evens */
    103     return MP_VAL;
    104 #endif
    105 #ifdef BN_MP_EXPTMOD_FAST_C
    106   }
    107 #endif
    108 }
    109 
    110 #endif
    111 
    112 /* Source: /cvs/libtom/libtommath/bn_mp_exptmod.c,v  */
    113 /* Revision: 1.5  */
    114 /* Date: 2006/12/28 01:25:13  */
    115