Mercurial > dropbear

comparison bn_mp_montgomery_reduce.c @ 142:d29b64170cf0 libtommath-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents 86e0b50a9b58
children
comparison
equal deleted inserted replaced
19:e1037a1e12e7 142:d29b64170cf0
1 #include <tommath.h>
2 #ifdef BN_MP_MONTGOMERY_REDUCE_C
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 * 4 *
3 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
5 * 7 *
10 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
11 * guarantee it works. 13 * guarantee it works.
12 * 14 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */ 16 */
15 #include <tommath.h>
16 17
17 /* computes xR**-1 == x (mod N) via Montgomery Reduction */ 18 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
18 int 19 int
19 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)
20 { 21 {
21 int ix, res, digs; 22 int ix, res, digs;
22 mp_digit mu; 23 mp_digit mu;
23 24
24 /* can the fast reduction [comba] method be used? 25 /* can the fast reduction [comba] method be used?
25 * 26 *
26 * Note that unlike in mp_mul you're safely allowed *less* 27 * Note that unlike in mul you're safely allowed *less*
27 * than the available columns [255 per default] since carries 28 * than the available columns [255 per default] since carries
28 * are fixed up in the inner loop. 29 * are fixed up in the inner loop.
29 */ 30 */
30 digs = n->used * 2 + 1; 31 digs = n->used * 2 + 1;
31 if ((digs < MP_WARRAY) && 32 if ((digs < MP_WARRAY) &&
44 45
45 for (ix = 0; ix < n->used; ix++) { 46 for (ix = 0; ix < n->used; ix++) {
46 /* mu = ai * rho mod b 47 /* mu = ai * rho mod b
47 * 48 *
48 * The value of rho must be precalculated via 49 * The value of rho must be precalculated via
49 * bn_mp_montgomery_setup() such that 50 * montgomery_setup() such that
50 * it equals -1/n0 mod b this allows the 51 * it equals -1/n0 mod b this allows the
51 * following inner loop to reduce the 52 * following inner loop to reduce the
52 * input one digit at a time 53 * input one digit at a time
53 */ 54 */
54 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);
108 return s_mp_sub (x, n, x); 109 return s_mp_sub (x, n, x);
109 } 110 }
110 111
111 return MP_OKAY; 112 return MP_OKAY;
112 } 113 }
114 #endif