Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_REDUCE_2K_L_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* reduces a modulo n where n is of the form 2**p - d
       7             :    This differs from reduce_2k since "d" can be larger
       8             :    than a single digit.
       9             : */
      10           0 : mp_err mp_reduce_2k_l(mp_int *a, const mp_int *n, const mp_int *d)
      11             : {
      12           0 :    mp_int q;
      13           0 :    mp_err err;
      14           0 :    int    p;
      15             : 
      16           0 :    if ((err = mp_init(&q)) != MP_OKAY) {
      17           0 :       return err;
      18             :    }
      19             : 
      20           0 :    p = mp_count_bits(n);
      21           0 : top:
      22             :    /* q = a/2**p, a = a mod 2**p */
      23           0 :    if ((err = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
      24           0 :       goto LBL_ERR;
      25             :    }
      26             : 
      27             :    /* q = q * d */
      28           0 :    if ((err = mp_mul(&q, d, &q)) != MP_OKAY) {
      29           0 :       goto LBL_ERR;
      30             :    }
      31             : 
      32             :    /* a = a + q */
      33           0 :    if ((err = s_mp_add(a, &q, a)) != MP_OKAY) {
      34           0 :       goto LBL_ERR;
      35             :    }
      36             : 
      37           0 :    if (mp_cmp_mag(a, n) != MP_LT) {
      38           0 :       if ((err = s_mp_sub(a, n, a)) != MP_OKAY) {
      39           0 :          goto LBL_ERR;
      40             :       }
      41           0 :       goto top;
      42             :    }
      43             : 
      44           0 : LBL_ERR:
      45           0 :    mp_clear(&q);
      46           0 :    return err;
      47             : }
      48             : 
      49             : #endif