mp_reduce_2k_l.c

   1 #include "tommath_private.h"
   2 #ifdef 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 mp_err mp_reduce_2k_l(mp_int *a, const mp_int *n, const mp_int *d)
  11 {
  12    mp_int q;
  13    mp_err err;
  14    int    p;
  15
  16    if ((err = mp_init(&q)) != MP_OKAY) {
  17       return err;
  18    }
  19
  20    p = mp_count_bits(n);
  21
  22    for (;;) {
  23       /* q = a/2**p, a = a mod 2**p */
  24       if ((err = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
  25          goto LBL_ERR;
  26       }
  27
  28       /* q = q * d */
  29       if ((err = mp_mul(&q, d, &q)) != MP_OKAY) {
  30          goto LBL_ERR;
  31       }
  32
  33       /* a = a + q */
  34       if ((err = s_mp_add(a, &q, a)) != MP_OKAY) {
  35          goto LBL_ERR;
  36       }
  37
  38       if (mp_cmp_mag(a, n) == MP_LT) {
  39          break;
  40       }
  41       if ((err = s_mp_sub(a, n, a)) != MP_OKAY) {
  42          goto LBL_ERR;
  43       }
  44
  45    }
  46
  47 LBL_ERR:
  48    mp_clear(&q);
  49    return err;
  50 }
  51
  52 #endif