| 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, [email protected], http://libtom.org |
| 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.4 $ */ |
| 94 |
/* $Date: 2006/12/28 01:25:13 $ */ |