Mercurial > dropbear

comparison libtommath/bn_mp_reduce.c @ 1436:60fc6476e044

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update to libtommath v1.0
author Matt Johnston <matt@ucc.asn.au>
date Sat, 24 Jun 2017 22:37:14 +0800
parents 5ff8218bcee9
children 8bba51a55704
comparison
equal deleted inserted replaced
1435:f849a5ca2efc 1436:60fc6476e044
1 #include <tommath.h> 1 #include <tommath_private.h>
2 #ifdef BN_MP_REDUCE_C 2 #ifdef BN_MP_REDUCE_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 * 4 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
13 * guarantee it works. 13 * guarantee it works.
14 * 14 *
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com 15 * Tom St Denis, [email protected], http://libtom.org
16 */ 16 */
17 17
18 /* reduces x mod m, assumes 0 < x < m**2, mu is 18 /* reduces x mod m, assumes 0 < x < m**2, mu is
19 * precomputed via mp_reduce_setup. 19 * precomputed via mp_reduce_setup.
20 * From HAC pp.604 Algorithm 14.42 20 * From HAC pp.604 Algorithm 14.42
21 */ 21 */
22 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu) 22 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu)
23 { 23 {
28 if ((res = mp_init_copy (&q, x)) != MP_OKAY) { 28 if ((res = mp_init_copy (&q, x)) != MP_OKAY) {
29 return res; 29 return res;
30 } 30 }
31 31
32 /* q1 = x / b**(k-1) */ 32 /* q1 = x / b**(k-1) */
33 mp_rshd (&q, um - 1); 33 mp_rshd (&q, um - 1);
34 34
35 /* according to HAC this optimization is ok */ 35 /* according to HAC this optimization is ok */
36 if (((unsigned long) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) { 36 if (((mp_digit) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) {
37 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) { 37 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) {
38 goto CLEANUP; 38 goto CLEANUP;
39 } 39 }
40 } else { 40 } else {
41 #ifdef BN_S_MP_MUL_HIGH_DIGS_C 41 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
44 } 44 }
45 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C) 45 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
46 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) { 46 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
47 goto CLEANUP; 47 goto CLEANUP;
48 } 48 }
49 #else 49 #else
50 { 50 {
51 res = MP_VAL; 51 res = MP_VAL;
52 goto CLEANUP; 52 goto CLEANUP;
53 } 53 }
54 #endif 54 #endif
55 } 55 }
56 56
57 /* q3 = q2 / b**(k+1) */ 57 /* q3 = q2 / b**(k+1) */
58 mp_rshd (&q, um + 1); 58 mp_rshd (&q, um + 1);
59 59
60 /* x = x mod b**(k+1), quick (no division) */ 60 /* x = x mod b**(k+1), quick (no division) */
61 if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) { 61 if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
62 goto CLEANUP; 62 goto CLEANUP;
63 } 63 }
85 while (mp_cmp (x, m) != MP_LT) { 85 while (mp_cmp (x, m) != MP_LT) {
86 if ((res = s_mp_sub (x, m, x)) != MP_OKAY) { 86 if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
87 goto CLEANUP; 87 goto CLEANUP;
88 } 88 }
89 } 89 }
90 90
91 CLEANUP: 91 CLEANUP:
92 mp_clear (&q); 92 mp_clear (&q);
93 93
94 return res; 94 return res;
95 } 95 }
96 #endif 96 #endif
97 97
98 /* $Source: /cvs/libtom/libtommath/bn_mp_reduce.c,v $ */ 98 /* $Source$ */
99 /* $Revision: 1.3 $ */ 99 /* $Revision$ */
100 /* $Date: 2006/03/31 14:18:44 $ */ 100 /* $Date$ */