Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 101 lines (87 sloc) 2.357 kB
e549ccf added libtommath-0.32
Tom St Denis authored
1 #include <tommath.h>
2 #ifdef BN_MP_REDUCE_C
57354e1 added libtommath-0.12
Tom St Denis authored
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 *
c1da6aa added libtommath-0.25
Tom St Denis authored
5 * LibTomMath is a library that provides multiple-precision
57354e1 added libtommath-0.12
Tom St Denis authored
6 * integer arithmetic as well as number theoretic functionality.
7 *
c1da6aa added libtommath-0.25
Tom St Denis authored
8 * The library was designed directly after the MPI library by
57354e1 added libtommath-0.12
Tom St Denis authored
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 *
333aebc added libtommath-0.41
Tom St Denis authored
15 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
57354e1 added libtommath-0.12
Tom St Denis authored
16 */
17
0ef44ce added libtommath-0.18
Tom St Denis authored
18 /* reduces x mod m, assumes 0 < x < m**2, mu is
19 * precomputed via mp_reduce_setup.
fd181cc added libtommath-0.17
Tom St Denis authored
20 * From HAC pp.604 Algorithm 14.42
57354e1 added libtommath-0.12
Tom St Denis authored
21 */
3d0fcaa added libtommath-0.34
Tom St Denis authored
22 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu)
57354e1 added libtommath-0.12
Tom St Denis authored
23 {
b66471f added libtommath-0.13
Tom St Denis authored
24 mp_int q;
25 int res, um = m->used;
57354e1 added libtommath-0.12
Tom St Denis authored
26
0ef44ce added libtommath-0.18
Tom St Denis authored
27 /* q = x */
57354e1 added libtommath-0.12
Tom St Denis authored
28 if ((res = mp_init_copy (&q, x)) != MP_OKAY) {
29 return res;
30 }
31
0ef44ce added libtommath-0.18
Tom St Denis authored
32 /* q1 = x / b**(k-1) */
fd181cc added libtommath-0.17
Tom St Denis authored
33 mp_rshd (&q, um - 1);
57354e1 added libtommath-0.12
Tom St Denis authored
34
49bef06 added libtommath-0.21
Tom St Denis authored
35 /* according to HAC this optimization is ok */
36 if (((unsigned long) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) {
57354e1 added libtommath-0.12
Tom St Denis authored
37 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) {
38 goto CLEANUP;
39 }
40 } else {
e549ccf added libtommath-0.32
Tom St Denis authored
41 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
fdfa2f4 added libtommath-0.35
Tom St Denis authored
42 if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
57354e1 added libtommath-0.12
Tom St Denis authored
43 goto CLEANUP;
44 }
e549ccf added libtommath-0.32
Tom St Denis authored
45 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
fdfa2f4 added libtommath-0.35
Tom St Denis authored
46 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
e549ccf added libtommath-0.32
Tom St Denis authored
47 goto CLEANUP;
48 }
49 #else
50 {
51 res = MP_VAL;
52 goto CLEANUP;
53 }
54 #endif
57354e1 added libtommath-0.12
Tom St Denis authored
55 }
56
0ef44ce added libtommath-0.18
Tom St Denis authored
57 /* q3 = q2 / b**(k+1) */
fd181cc added libtommath-0.17
Tom St Denis authored
58 mp_rshd (&q, um + 1);
57354e1 added libtommath-0.12
Tom St Denis authored
59
0ef44ce added libtommath-0.18
Tom St Denis authored
60 /* x = x mod b**(k+1), quick (no division) */
57354e1 added libtommath-0.12
Tom St Denis authored
61 if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
62 goto CLEANUP;
63 }
64
0ef44ce added libtommath-0.18
Tom St Denis authored
65 /* q = q * m mod b**(k+1), quick (no division) */
57354e1 added libtommath-0.12
Tom St Denis authored
66 if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) {
67 goto CLEANUP;
68 }
69
70 /* x = x - q */
fd181cc added libtommath-0.17
Tom St Denis authored
71 if ((res = mp_sub (x, &q, x)) != MP_OKAY) {
57354e1 added libtommath-0.12
Tom St Denis authored
72 goto CLEANUP;
fd181cc added libtommath-0.17
Tom St Denis authored
73 }
57354e1 added libtommath-0.12
Tom St Denis authored
74
0ef44ce added libtommath-0.18
Tom St Denis authored
75 /* If x < 0, add b**(k+1) to it */
57354e1 added libtommath-0.12
Tom St Denis authored
76 if (mp_cmp_d (x, 0) == MP_LT) {
77 mp_set (&q, 1);
78 if ((res = mp_lshd (&q, um + 1)) != MP_OKAY)
79 goto CLEANUP;
80 if ((res = mp_add (x, &q, x)) != MP_OKAY)
81 goto CLEANUP;
82 }
83
84 /* Back off if it's too big */
85 while (mp_cmp (x, m) != MP_LT) {
fd181cc added libtommath-0.17
Tom St Denis authored
86 if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
49bef06 added libtommath-0.21
Tom St Denis authored
87 goto CLEANUP;
fd181cc added libtommath-0.17
Tom St Denis authored
88 }
57354e1 added libtommath-0.12
Tom St Denis authored
89 }
0ef44ce added libtommath-0.18
Tom St Denis authored
90
57354e1 added libtommath-0.12
Tom St Denis authored
91 CLEANUP:
92 mp_clear (&q);
93
94 return res;
95 }
e549ccf added libtommath-0.32
Tom St Denis authored
96 #endif
9294e79 added libtommath-0.36
Tom St Denis authored
97
98 /* $Source$ */
99 /* $Revision$ */
100 /* $Date$ */
Something went wrong with that request. Please try again.