1 /* $NetBSD: bn_mp_reduce.c,v 1.1.1.2 2014/04/24 12:45:31 pettai Exp $ */
2
3 #include <tommath.h>
4 #ifdef BN_MP_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 /* reduces x mod m, assumes 0 < x < m**2, mu is
21 * precomputed via mp_reduce_setup.
22 * From HAC pp.604 Algorithm 14.42
23 */
mp_reduce(mp_int * x,mp_int * m,mp_int * mu)24 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu)
25 {
26 mp_int q;
27 int res, um = m->used;
28
29 /* q = x */
30 if ((res = mp_init_copy (&q, x)) != MP_OKAY) {
31 return res;
32 }
33
34 /* q1 = x / b**(k-1) */
35 mp_rshd (&q, um - 1);
36
37 /* according to HAC this optimization is ok */
38 if (((unsigned long) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) {
39 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) {
40 goto CLEANUP;
41 }
42 } else {
43 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
44 if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
45 goto CLEANUP;
46 }
47 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
48 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
49 goto CLEANUP;
50 }
51 #else
52 {
53 res = MP_VAL;
54 goto CLEANUP;
55 }
56 #endif
57 }
58
59 /* q3 = q2 / b**(k+1) */
60 mp_rshd (&q, um + 1);
61
62 /* x = x mod b**(k+1), quick (no division) */
63 if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
64 goto CLEANUP;
65 }
66
67 /* q = q * m mod b**(k+1), quick (no division) */
68 if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) {
69 goto CLEANUP;
70 }
71
72 /* x = x - q */
73 if ((res = mp_sub (x, &q, x)) != MP_OKAY) {
74 goto CLEANUP;
75 }
76
77 /* If x < 0, add b**(k+1) to it */
78 if (mp_cmp_d (x, 0) == MP_LT) {
79 mp_set (&q, 1);
80 if ((res = mp_lshd (&q, um + 1)) != MP_OKAY)
81 goto CLEANUP;
82 if ((res = mp_add (x, &q, x)) != MP_OKAY)
83 goto CLEANUP;
84 }
85
86 /* Back off if it's too big */
87 while (mp_cmp (x, m) != MP_LT) {
88 if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
89 goto CLEANUP;
90 }
91 }
92
93 CLEANUP:
94 mp_clear (&q);
95
96 return res;
97 }
98 #endif
99
100 /* Source: /cvs/libtom/libtommath/bn_mp_reduce.c,v */
101 /* Revision: 1.4 */
102 /* Date: 2006/12/28 01:25:13 */
103