libs/libtommath/bn_mp_dr_reduce.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_DR_REDUCE_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 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
  19  *
  20  * Based on algorithm from the paper
  21  *
  22  * "Generating Efficient Primes for Discrete Log Cryptosystems"
  23  *                 Chae Hoon Lim, Pil Joong Lee,
  24  *          POSTECH Information Research Laboratories
  25  *
  26  * The modulus must be of a special format [see manual]
  27  *
  28  * Has been modified to use algorithm 7.10 from the LTM book instead
  29  *
  30  * Input x must be in the range 0 <= x <= (n-1)**2
  31  */
  32 int
  33 mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
  34 {
  35   int      err, i, m;
  36   mp_word  r;
  37   mp_digit mu, *tmpx1, *tmpx2;
  38
  39   /* m = digits in modulus */
  40   m = n->used;
  41
  42   /* ensure that "x" has at least 2m digits */
  43   if (x->alloc < m + m) {
  44     if ((err = mp_grow (x, m + m)) != MP_OKAY) {
  45       return err;
  46     }
  47   }
  48
  49 /* top of loop, this is where the code resumes if
  50  * another reduction pass is required.
  51  */
  52 top:
  53   /* aliases for digits */
  54   /* alias for lower half of x */
  55   tmpx1 = x->dp;
  56
  57   /* alias for upper half of x, or x/B**m */
  58   tmpx2 = x->dp + m;
  59
  60   /* set carry to zero */
  61   mu = 0;
  62
  63   /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
  64   for (i = 0; i < m; i++) {
  65       r         = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu;
  66       *tmpx1++  = (mp_digit)(r & MP_MASK);
  67       mu        = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
  68   }
  69
  70   /* set final carry */
  71   *tmpx1++ = mu;
  72
  73   /* zero words above m */
  74   for (i = m + 1; i < x->used; i++) {
  75       *tmpx1++ = 0;
  76   }
  77
  78   /* clamp, sub and return */
  79   mp_clamp (x);
  80
  81   /* if x >= n then subtract and reduce again
  82    * Each successive "recursion" makes the input smaller and smaller.
  83    */
  84   if (mp_cmp_mag (x, n) != MP_LT) {
  85     s_mp_sub(x, n, x);
  86     goto top;
  87   }
  88   return MP_OKAY;
  89 }
  90 #endif
  91
  92 /* $Source: /cvs/libtom/libtommath/bn_mp_dr_reduce.c,v $ */
  93 /* $Revision: 1.3 $ */
  94 /* $Date: 2006/03/31 14:18:44 $ */