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 (at) 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 $ */ 95
