/src/dropbear/libtommath/bn_mp_montgomery_setup.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_MONTGOMERY_SETUP_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* setups the montgomery reduction stuff */ |
7 | | mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho) |
8 | 3.32k | { |
9 | 3.32k | mp_digit x, b; |
10 | | |
11 | | /* fast inversion mod 2**k |
12 | | * |
13 | | * Based on the fact that |
14 | | * |
15 | | * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n) |
16 | | * => 2*X*A - X*X*A*A = 1 |
17 | | * => 2*(1) - (1) = 1 |
18 | | */ |
19 | 3.32k | b = n->dp[0]; |
20 | | |
21 | 3.32k | if ((b & 1u) == 0u) { |
22 | 0 | return MP_VAL; |
23 | 0 | } |
24 | | |
25 | 3.32k | x = (((b + 2u) & 4u) << 1) + b; /* here x*a==1 mod 2**4 */ |
26 | 3.32k | x *= 2u - (b * x); /* here x*a==1 mod 2**8 */ |
27 | 3.32k | #if !defined(MP_8BIT) |
28 | 3.32k | x *= 2u - (b * x); /* here x*a==1 mod 2**16 */ |
29 | 3.32k | #endif |
30 | 3.32k | #if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT)) |
31 | 3.32k | x *= 2u - (b * x); /* here x*a==1 mod 2**32 */ |
32 | 3.32k | #endif |
33 | 3.32k | #ifdef MP_64BIT |
34 | 3.32k | x *= 2u - (b * x); /* here x*a==1 mod 2**64 */ |
35 | 3.32k | #endif |
36 | | |
37 | | /* rho = -1/m mod b */ |
38 | 3.32k | *rho = (mp_digit)(((mp_word)1 << (mp_word)MP_DIGIT_BIT) - x) & MP_MASK; |
39 | | |
40 | 3.32k | return MP_OKAY; |
41 | 3.32k | } |
42 | | #endif |