Mercurial > dropbear

comparison libtommath/bn_mp_montgomery_reduce.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.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 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* computes xR**-1 == x (mod N) via Montgomery Reduction */ 6 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
16 int mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho) 7 mp_err mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho)
17 { 8 {
18 int ix, res, digs; 9 int ix, digs;
10 mp_err err;
19 mp_digit mu; 11 mp_digit mu;
20 12
21 /* can the fast reduction [comba] method be used? 13 /* can the fast reduction [comba] method be used?
22 * 14 *
23 * Note that unlike in mul you're safely allowed *less* 15 * Note that unlike in mul you're safely allowed *less*
24 * than the available columns [255 per default] since carries 16 * than the available columns [255 per default] since carries
25 * are fixed up in the inner loop. 17 * are fixed up in the inner loop.
26 */ 18 */
27 digs = (n->used * 2) + 1; 19 digs = (n->used * 2) + 1;
28 if ((digs < (int)MP_WARRAY) && 20 if ((digs < MP_WARRAY) &&
29 (x->used <= (int)MP_WARRAY) && 21 (x->used <= MP_WARRAY) &&
30 (n->used < 22 (n->used < MP_MAXFAST)) {
31 (int)(1u << (((size_t)CHAR_BIT * sizeof(mp_word)) - (2u * (size_t)DIGIT_BIT))))) { 23 return s_mp_montgomery_reduce_fast(x, n, rho);
32 return fast_mp_montgomery_reduce(x, n, rho);
33 } 24 }
34 25
35 /* grow the input as required */ 26 /* grow the input as required */
36 if (x->alloc < digs) { 27 if (x->alloc < digs) {
37 if ((res = mp_grow(x, digs)) != MP_OKAY) { 28 if ((err = mp_grow(x, digs)) != MP_OKAY) {
38 return res; 29 return err;
39 } 30 }
40 } 31 }
41 x->used = digs; 32 x->used = digs;
42 33
43 for (ix = 0; ix < n->used; ix++) { 34 for (ix = 0; ix < n->used; ix++) {
71 /* compute product and sum */ 62 /* compute product and sum */
72 r = ((mp_word)mu * (mp_word)*tmpn++) + 63 r = ((mp_word)mu * (mp_word)*tmpn++) +
73 (mp_word)u + (mp_word)*tmpx; 64 (mp_word)u + (mp_word)*tmpx;
74 65
75 /* get carry */ 66 /* get carry */
76 u = (mp_digit)(r >> (mp_word)DIGIT_BIT); 67 u = (mp_digit)(r >> (mp_word)MP_DIGIT_BIT);
77 68
78 /* fix digit */ 69 /* fix digit */
79 *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK); 70 *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK);
80 } 71 }
81 /* At this point the ix'th digit of x should be zero */ 72 /* At this point the ix'th digit of x should be zero */
82 73
83 74
84 /* propagate carries upwards as required*/ 75 /* propagate carries upwards as required*/
85 while (u != 0u) { 76 while (u != 0u) {
86 *tmpx += u; 77 *tmpx += u;
87 u = *tmpx >> DIGIT_BIT; 78 u = *tmpx >> MP_DIGIT_BIT;
88 *tmpx++ &= MP_MASK; 79 *tmpx++ &= MP_MASK;
89 } 80 }
90 } 81 }
91 } 82 }
92 83
107 } 98 }
108 99
109 return MP_OKAY; 100 return MP_OKAY;
110 } 101 }
111 #endif 102 #endif
112
113 /* ref: HEAD -> master, tag: v1.1.0 */
114 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
115 /* commit time: 2019-01-28 20:32:32 +0100 */