c3-lang/libtommath/mp_montgomery_setup.c
Branch
-
Show log
Commit
-
Hash : 7a68f128
Author :
Date : 2019-10-19T16:24:39
Execute move.sh - Rename files from bn_* to match the function names. * git blame <renamed-file> is not affected * git log --follow <renamed-file> can be used to show log across renames
-
mp_montgomery_setup.c
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
#include "tommath_private.h" #ifdef MP_MONTGOMERY_SETUP_C /* LibTomMath, multiple-precision integer library -- Tom St Denis */ /* SPDX-License-Identifier: Unlicense */ /* setups the montgomery reduction stuff */ mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho) { mp_digit x, b; /* fast inversion mod 2**k * * Based on the fact that * * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n) * => 2*X*A - X*X*A*A = 1 * => 2*(1) - (1) = 1 */ b = n->dp[0]; if ((b & 1u) == 0u) { return MP_VAL; } x = (((b + 2u) & 4u) << 1) + b; /* here x*a==1 mod 2**4 */ x *= 2u - (b * x); /* here x*a==1 mod 2**8 */ x *= 2u - (b * x); /* here x*a==1 mod 2**16 */ #if defined(MP_64BIT) || !(defined(MP_16BIT)) x *= 2u - (b * x); /* here x*a==1 mod 2**32 */ #endif #ifdef MP_64BIT x *= 2u - (b * x); /* here x*a==1 mod 2**64 */ #endif /* rho = -1/m mod b */ *rho = (mp_digit)(((mp_word)1 << (mp_word)MP_DIGIT_BIT) - x) & MP_MASK; return MP_OKAY; } #endif