libs/libtommath/bn_mp_reduce_2k_l.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_REDUCE_2K_L_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 /* reduces a modulo n where n is of the form 2**p - d
  19    This differs from reduce_2k since "d" can be larger
  20    than a single digit.
  21 */
  22 int mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d)
  23 {
  24    mp_int q;
  25    int    p, res;
  26
  27    if ((res = mp_init(&q)) != MP_OKAY) {
  28       return res;
  29    }
  30
  31    p = mp_count_bits(n);
  32 top:
  33    /* q = a/2**p, a = a mod 2**p */
  34    if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
  35       goto ERR;
  36    }
  37
  38    /* q = q * d */
  39    if ((res = mp_mul(&q, d, &q)) != MP_OKAY) {
  40       goto ERR;
  41    }
  42
  43    /* a = a + q */
  44    if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
  45       goto ERR;
  46    }
  47
  48    if (mp_cmp_mag(a, n) != MP_LT) {
  49       s_mp_sub(a, n, a);
  50       goto top;
  51    }
  52
  53 ERR:
  54    mp_clear(&q);
  55    return res;
  56 }
  57
  58 #endif
  59
  60 /* $Source: /cvs/libtom/libtommath/bn_mp_reduce_2k_l.c,v $ */
  61 /* $Revision: 1.3 $ */
  62 /* $Date: 2006/03/31 14:18:44 $ */