Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_DR_REDUCE_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
       7             :  *
       8             :  * Based on algorithm from the paper
       9             :  *
      10             :  * "Generating Efficient Primes for Discrete Log Cryptosystems"
      11             :  *                 Chae Hoon Lim, Pil Joong Lee,
      12             :  *          POSTECH Information Research Laboratories
      13             :  *
      14             :  * The modulus must be of a special format [see manual]
      15             :  *
      16             :  * Has been modified to use algorithm 7.10 from the LTM book instead
      17             :  *
      18             :  * Input x must be in the range 0 <= x <= (n-1)**2
      19             :  */
      20           0 : mp_err mp_dr_reduce(mp_int *x, const mp_int *n, mp_digit k)
      21             : {
      22           0 :    mp_err      err;
      23           0 :    int i, m;
      24           0 :    mp_word  r;
      25           0 :    mp_digit mu, *tmpx1, *tmpx2;
      26             : 
      27             :    /* m = digits in modulus */
      28           0 :    m = n->used;
      29             : 
      30             :    /* ensure that "x" has at least 2m digits */
      31           0 :    if (x->alloc < (m + m)) {
      32           0 :       if ((err = mp_grow(x, m + m)) != MP_OKAY) {
      33           0 :          return err;
      34             :       }
      35             :    }
      36             : 
      37             :    /* top of loop, this is where the code resumes if
      38             :     * another reduction pass is required.
      39             :     */
      40           0 : top:
      41             :    /* aliases for digits */
      42             :    /* alias for lower half of x */
      43           0 :    tmpx1 = x->dp;
      44             : 
      45             :    /* alias for upper half of x, or x/B**m */
      46           0 :    tmpx2 = x->dp + m;
      47             : 
      48             :    /* set carry to zero */
      49           0 :    mu = 0;
      50             : 
      51             :    /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
      52           0 :    for (i = 0; i < m; i++) {
      53           0 :       r         = ((mp_word)*tmpx2++ * (mp_word)k) + *tmpx1 + mu;
      54           0 :       *tmpx1++  = (mp_digit)(r & MP_MASK);
      55           0 :       mu        = (mp_digit)(r >> ((mp_word)MP_DIGIT_BIT));
      56             :    }
      57             : 
      58             :    /* set final carry */
      59           0 :    *tmpx1++ = mu;
      60             : 
      61             :    /* zero words above m */
      62           0 :    MP_ZERO_DIGITS(tmpx1, (x->used - m) - 1);
      63             : 
      64             :    /* clamp, sub and return */
      65           0 :    mp_clamp(x);
      66             : 
      67             :    /* if x >= n then subtract and reduce again
      68             :     * Each successive "recursion" makes the input smaller and smaller.
      69             :     */
      70           0 :    if (mp_cmp_mag(x, n) != MP_LT) {
      71           0 :       if ((err = s_mp_sub(x, n, x)) != MP_OKAY) {
      72           0 :          return err;
      73             :       }
      74           0 :       goto top;
      75             :    }
      76           0 :    return MP_OKAY;
      77             : }
      78             : #endif