Mercurial > dropbear

comparison libtommath/bn_mp_montgomery_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_MONTGOMERY_REDUCE_C 2 #ifdef BN_MP_MONTGOMERY_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 /* computes xR**-1 == x (mod N) via Montgomery Reduction */ 18 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
19 int 19 int
20 mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho) 20 mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
26 * 26 *
27 * Note that unlike in mul you're safely allowed *less* 27 * Note that unlike in mul you're safely allowed *less*
28 * than the available columns [255 per default] since carries 28 * than the available columns [255 per default] since carries
29 * are fixed up in the inner loop. 29 * are fixed up in the inner loop.
30 */ 30 */
31 digs = n->used * 2 + 1; 31 digs = (n->used * 2) + 1;
32 if ((digs < MP_WARRAY) && 32 if ((digs < MP_WARRAY) &&
33 n->used < 33 (n->used <
34 (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 34 (1 << ((CHAR_BIT * sizeof(mp_word)) - (2 * DIGIT_BIT))))) {
35 return fast_mp_montgomery_reduce (x, n, rho); 35 return fast_mp_montgomery_reduce (x, n, rho);
36 } 36 }
37 37
38 /* grow the input as required */ 38 /* grow the input as required */
39 if (x->alloc < digs) { 39 if (x->alloc < digs) {
50 * montgomery_setup() such that 50 * montgomery_setup() such that
51 * it equals -1/n0 mod b this allows the 51 * it equals -1/n0 mod b this allows the
52 * following inner loop to reduce the 52 * following inner loop to reduce the
53 * input one digit at a time 53 * input one digit at a time
54 */ 54 */
55 mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK); 55 mu = (mp_digit) (((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK);
56 56
57 /* a = a + mu * m * b**i */ 57 /* a = a + mu * m * b**i */
58 { 58 {
59 register int iy; 59 int iy;
60 register mp_digit *tmpn, *tmpx, u; 60 mp_digit *tmpn, *tmpx, u;
61 register mp_word r; 61 mp_word r;
62 62
63 /* alias for digits of the modulus */ 63 /* alias for digits of the modulus */
64 tmpn = n->dp; 64 tmpn = n->dp;
65 65
66 /* alias for the digits of x [the input] */ 66 /* alias for the digits of x [the input] */
70 u = 0; 70 u = 0;
71 71
72 /* Multiply and add in place */ 72 /* Multiply and add in place */
73 for (iy = 0; iy < n->used; iy++) { 73 for (iy = 0; iy < n->used; iy++) {
74 /* compute product and sum */ 74 /* compute product and sum */
75 r = ((mp_word)mu) * ((mp_word)*tmpn++) + 75 r = ((mp_word)mu * (mp_word)*tmpn++) +
76 ((mp_word) u) + ((mp_word) * tmpx); 76 (mp_word) u + (mp_word) *tmpx;
77 77
78 /* get carry */ 78 /* get carry */
79 u = (mp_digit)(r >> ((mp_word) DIGIT_BIT)); 79 u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
80 80
81 /* fix digit */ 81 /* fix digit */
83 } 83 }
84 /* At this point the ix'th digit of x should be zero */ 84 /* At this point the ix'th digit of x should be zero */
85 85
86 86
87 /* propagate carries upwards as required*/ 87 /* propagate carries upwards as required*/
88 while (u) { 88 while (u != 0) {
89 *tmpx += u; 89 *tmpx += u;
90 u = *tmpx >> DIGIT_BIT; 90 u = *tmpx >> DIGIT_BIT;
91 *tmpx++ &= MP_MASK; 91 *tmpx++ &= MP_MASK;
92 } 92 }
93 } 93 }
111 111
112 return MP_OKAY; 112 return MP_OKAY;
113 } 113 }
114 #endif 114 #endif
115 115
116 /* $Source: /cvs/libtom/libtommath/bn_mp_montgomery_reduce.c,v $ */ 116 /* $Source$ */
117 /* $Revision: 1.3 $ */ 117 /* $Revision$ */
118 /* $Date: 2006/03/31 14:18:44 $ */ 118 /* $Date$ */