Line data    Source code

       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         922 : mp_err mp_montgomery_setup(const mp_int *n, mp_digit *rho)
       8             : {
       9          32 :    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         922 :    b = n->dp[0];
      20             : 
      21         922 :    if ((b & 1u) == 0u) {
      22           0 :       return MP_VAL;
      23             :    }
      24             : 
      25         922 :    x = (((b + 2u) & 4u) << 1) + b; /* here x*a==1 mod 2**4 */
      26         922 :    x *= 2u - (b * x);              /* here x*a==1 mod 2**8 */
      27             : #if !defined(MP_8BIT)
      28         922 :    x *= 2u - (b * x);              /* here x*a==1 mod 2**16 */
      29             : #endif
      30             : #if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT))
      31         922 :    x *= 2u - (b * x);              /* here x*a==1 mod 2**32 */
      32             : #endif
      33             : #ifdef MP_64BIT
      34         922 :    x *= 2u - (b * x);              /* here x*a==1 mod 2**64 */
      35             : #endif
      36             : 
      37             :    /* rho = -1/m mod b */
      38         922 :    *rho = (mp_digit)(((mp_word)1 << (mp_word)MP_DIGIT_BIT) - x) & MP_MASK;
      39             : 
      40         922 :    return MP_OKAY;
      41             : }
      42             : #endif