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