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