libs/libtommath/bn_mp_reduce_2k.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_REDUCE_2K_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 int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d)
  20 {
  21    mp_int q;
  22    int    p, res;
  23
  24    if ((res = mp_init(&q)) != MP_OKAY) {
  25       return res;
  26    }
  27
  28    p = mp_count_bits(n);
  29 top:
  30    /* q = a/2**p, a = a mod 2**p */
  31    if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
  32       goto ERR;
  33    }
  34
  35    if (d != 1) {
  36       /* q = q * d */
  37       if ((res = mp_mul_d(&q, d, &q)) != MP_OKAY) {
  38          goto ERR;
  39       }
  40    }
  41
  42    /* a = a + q */
  43    if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
  44       goto ERR;
  45    }
  46
  47    if (mp_cmp_mag(a, n) != MP_LT) {
  48       s_mp_sub(a, n, a);
  49       goto top;
  50    }
  51
  52 ERR:
  53    mp_clear(&q);
  54    return res;
  55 }
  56
  57 #endif
  58
  59 /* $Source: /cvs/libtom/libtommath/bn_mp_reduce_2k.c,v $ */
  60 /* $Revision: 1.3 $ */
  61 /* $Date: 2006/03/31 14:18:44 $ */