|
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" |
|
|
23 * Chae Hoon Lim, Pil Loong 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 } |
|
142
|
90 #endif |
