Mercurial > dropbear
annotate bn_mp_dr_reduce.c @ 203:e109027b9edf libtommath LTM_DB_0.46 LTM_DB_0.47
Don't remove ~ files on make clean (and find -type was wrong anyway)
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 11 May 2005 16:27:28 +0000 |
| parents | d8254fc979e9 |
| children |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_MP_DR_REDUCE_C | |
| 2 | 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://math.libtomcrypt.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" | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
23 * Chae Hoon Lim, Pil Joong Lee, |
| 2 | 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 } | |
| 142 | 90 #endif |