Mercurial > dropbear
comparison libtommath/bn_mp_montgomery_setup.c @ 1739:13d834efc376 fuzz
merge from main
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Thu, 15 Oct 2020 19:55:15 +0800 |
parents | 1051e4eea25a |
children |
comparison
equal
deleted
inserted
replaced
1562:768ebf737aa0 | 1739:13d834efc376 |
---|---|
1 #include <tommath_private.h> | 1 #include "tommath_private.h" |
2 #ifdef BN_MP_MONTGOMERY_SETUP_C | 2 #ifdef BN_MP_MONTGOMERY_SETUP_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 * The library is free for all purposes without any express | |
13 * guarantee it works. | |
14 * | |
15 * Tom St Denis, [email protected], http://libtom.org | |
16 */ | |
17 | 5 |
18 /* setups the montgomery reduction stuff */ | 6 /* setups the montgomery reduction stuff */ |
19 int | 7 mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho) |
20 mp_montgomery_setup (mp_int * n, mp_digit * rho) | |
21 { | 8 { |
22 mp_digit x, b; | 9 mp_digit x, b; |
23 | 10 |
24 /* fast inversion mod 2**k | 11 /* fast inversion mod 2**k |
25 * | 12 * |
26 * Based on the fact that | 13 * Based on the fact that |
27 * | 14 * |
28 * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n) | 15 * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n) |
29 * => 2*X*A - X*X*A*A = 1 | 16 * => 2*X*A - X*X*A*A = 1 |
30 * => 2*(1) - (1) = 1 | 17 * => 2*(1) - (1) = 1 |
31 */ | 18 */ |
32 b = n->dp[0]; | 19 b = n->dp[0]; |
33 | 20 |
34 if ((b & 1) == 0) { | 21 if ((b & 1u) == 0u) { |
35 return MP_VAL; | 22 return MP_VAL; |
36 } | 23 } |
37 | 24 |
38 x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */ | 25 x = (((b + 2u) & 4u) << 1) + b; /* here x*a==1 mod 2**4 */ |
39 x *= 2 - (b * x); /* here x*a==1 mod 2**8 */ | 26 x *= 2u - (b * x); /* here x*a==1 mod 2**8 */ |
40 #if !defined(MP_8BIT) | 27 #if !defined(MP_8BIT) |
41 x *= 2 - (b * x); /* here x*a==1 mod 2**16 */ | 28 x *= 2u - (b * x); /* here x*a==1 mod 2**16 */ |
42 #endif | 29 #endif |
43 #if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT)) | 30 #if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT)) |
44 x *= 2 - (b * x); /* here x*a==1 mod 2**32 */ | 31 x *= 2u - (b * x); /* here x*a==1 mod 2**32 */ |
45 #endif | 32 #endif |
46 #ifdef MP_64BIT | 33 #ifdef MP_64BIT |
47 x *= 2 - (b * x); /* here x*a==1 mod 2**64 */ | 34 x *= 2u - (b * x); /* here x*a==1 mod 2**64 */ |
48 #endif | 35 #endif |
49 | 36 |
50 /* rho = -1/m mod b */ | 37 /* rho = -1/m mod b */ |
51 *rho = (mp_digit)(((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK; | 38 *rho = (mp_digit)(((mp_word)1 << (mp_word)MP_DIGIT_BIT) - x) & MP_MASK; |
52 | 39 |
53 return MP_OKAY; | 40 return MP_OKAY; |
54 } | 41 } |
55 #endif | 42 #endif |
56 | |
57 /* ref: $Format:%D$ */ | |
58 /* git commit: $Format:%H$ */ | |
59 /* commit time: $Format:%ai$ */ |