|
1
|
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
|
|
2 * |
|
|
3 * LibTomMath is a library that provides multiple-precision |
|
|
4 * integer arithmetic as well as number theoretic functionality. |
|
|
5 * |
|
|
6 * The library was designed directly after the MPI library by |
|
|
7 * Michael Fromberger but has been written from scratch with |
|
|
8 * additional optimizations in place. |
|
|
9 * |
|
|
10 * The library is free for all purposes without any express |
|
|
11 * guarantee it works. |
|
|
12 * |
|
|
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org |
|
|
14 */ |
|
|
15 #include <tommath.h> |
|
|
16 |
|
|
17 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. |
|
|
18 * |
|
|
19 * Based on algorithm from the paper |
|
|
20 * |
|
|
21 * "Generating Efficient Primes for Discrete Log Cryptosystems" |
|
|
22 * Chae Hoon Lim, Pil Loong Lee, |
|
|
23 * POSTECH Information Research Laboratories |
|
|
24 * |
|
|
25 * The modulus must be of a special format [see manual] |
|
|
26 * |
|
|
27 * Has been modified to use algorithm 7.10 from the LTM book instead |
|
|
28 * |
|
|
29 * Input x must be in the range 0 <= x <= (n-1)**2 |
|
|
30 */ |
|
|
31 int |
|
|
32 mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k) |
|
|
33 { |
|
|
34 int err, i, m; |
|
|
35 mp_word r; |
|
|
36 mp_digit mu, *tmpx1, *tmpx2; |
|
|
37 |
|
|
38 /* m = digits in modulus */ |
|
|
39 m = n->used; |
|
|
40 |
|
|
41 /* ensure that "x" has at least 2m digits */ |
|
|
42 if (x->alloc < m + m) { |
|
|
43 if ((err = mp_grow (x, m + m)) != MP_OKAY) { |
|
|
44 return err; |
|
|
45 } |
|
|
46 } |
|
|
47 |
|
|
48 /* top of loop, this is where the code resumes if |
|
|
49 * another reduction pass is required. |
|
|
50 */ |
|
|
51 top: |
|
|
52 /* aliases for digits */ |
|
|
53 /* alias for lower half of x */ |
|
|
54 tmpx1 = x->dp; |
|
|
55 |
|
|
56 /* alias for upper half of x, or x/B**m */ |
|
|
57 tmpx2 = x->dp + m; |
|
|
58 |
|
|
59 /* set carry to zero */ |
|
|
60 mu = 0; |
|
|
61 |
|
|
62 /* compute (x mod B**m) + k * [x/B**m] inline and inplace */ |
|
|
63 for (i = 0; i < m; i++) { |
|
|
64 r = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu; |
|
|
65 *tmpx1++ = (mp_digit)(r & MP_MASK); |
|
|
66 mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT)); |
|
|
67 } |
|
|
68 |
|
|
69 /* set final carry */ |
|
|
70 *tmpx1++ = mu; |
|
|
71 |
|
|
72 /* zero words above m */ |
|
|
73 for (i = m + 1; i < x->used; i++) { |
|
|
74 *tmpx1++ = 0; |
|
|
75 } |
|
|
76 |
|
|
77 /* clamp, sub and return */ |
|
|
78 mp_clamp (x); |
|
|
79 |
|
|
80 /* if x >= n then subtract and reduce again |
|
|
81 * Each successive "recursion" makes the input smaller and smaller. |
|
|
82 */ |
|
|
83 if (mp_cmp_mag (x, n) != MP_LT) { |
|
|
84 s_mp_sub(x, n, x); |
|
|
85 goto top; |
|
|
86 } |
|
|
87 return MP_OKAY; |
|
|
88 } |
