mp_montgomery_calc_normalization.c

   1 #include "tommath_private.h"
   2 #ifdef MP_MONTGOMERY_CALC_NORMALIZATION_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /*
   7  * shifts with subtractions when the result is greater than b.
   8  *
   9  * The method is slightly modified to shift B unconditionally upto just under
  10  * the leading bit of b.  This saves a lot of multiple precision shifting.
  11  */
  12 mp_err mp_montgomery_calc_normalization(mp_int *a, const mp_int *b)
  13 {
  14    int    x, bits;
  15    mp_err err;
  16
  17    /* how many bits of last digit does b use */
  18    bits = mp_count_bits(b) % MP_DIGIT_BIT;
  19
  20    if (b->used > 1) {
  21       if ((err = mp_2expt(a, ((b->used - 1) * MP_DIGIT_BIT) + bits - 1)) != MP_OKAY) {
  22          return err;
  23       }
  24    } else {
  25       mp_set(a, 1uL);
  26       bits = 1;
  27    }
  28
  29    /* now compute C = A * B mod b */
  30    for (x = bits - 1; x < (int)MP_DIGIT_BIT; x++) {
  31       if ((err = mp_mul_2(a, a)) != MP_OKAY) {
  32          return err;
  33       }
  34       if (mp_cmp_mag(a, b) != MP_LT) {
  35          if ((err = s_mp_sub(a, b, a)) != MP_OKAY) {
  36             return err;
  37          }
  38       }
  39    }
  40
  41    return MP_OKAY;
  42 }
  43 #endif