crypto/external/bsd/heimdal/dist/lib/hcrypto/libtommath/bn_mp_reduce.c

   1 /*      $NetBSD: bn_mp_reduce.c,v 1.1.1.2 2014/04/24 12:45:31 pettai Exp $      */
   2
   3 #include <tommath.h>
   4 #ifdef BN_MP_REDUCE_C
   5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   6  *
   7  * LibTomMath is a library that provides multiple-precision
   8  * integer arithmetic as well as number theoretic functionality.
   9  *
  10  * The library was designed directly after the MPI library by
  11  * Michael Fromberger but has been written from scratch with
  12  * additional optimizations in place.
  13  *
  14  * The library is free for all purposes without any express
  15  * guarantee it works.
  16  *
  17  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  18  */
  19
  20 /* reduces x mod m, assumes 0 < x < m**2, mu is
  21  * precomputed via mp_reduce_setup.
  22  * From HAC pp.604 Algorithm 14.42
  23  */
  24 int mp_reduce (mp_int * x, mp_int * m, mp_int * mu)
  25 {
  26   mp_int  q;
  27   int     res, um = m->used;
  28
  29   /* q = x */
  30   if ((res = mp_init_copy (&q, x)) != MP_OKAY) {
  31     return res;
  32   }
  33
  34   /* q1 = x / b**(k-1)  */
  35   mp_rshd (&q, um - 1);
  36
  37   /* according to HAC this optimization is ok */
  38   if (((unsigned long) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) {
  39     if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) {
  40       goto CLEANUP;
  41     }
  42   } else {
  43 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
  44     if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
  45       goto CLEANUP;
  46     }
  47 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
  48     if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
  49       goto CLEANUP;
  50     }
  51 #else
  52     {
  53       res = MP_VAL;
  54       goto CLEANUP;
  55     }
  56 #endif
  57   }
  58
  59   /* q3 = q2 / b**(k+1) */
  60   mp_rshd (&q, um + 1);
  61
  62   /* x = x mod b**(k+1), quick (no division) */
  63   if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
  64     goto CLEANUP;
  65   }
  66
  67   /* q = q * m mod b**(k+1), quick (no division) */
  68   if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) {
  69     goto CLEANUP;
  70   }
  71
  72   /* x = x - q */
  73   if ((res = mp_sub (x, &q, x)) != MP_OKAY) {
  74     goto CLEANUP;
  75   }
  76
  77   /* If x < 0, add b**(k+1) to it */
  78   if (mp_cmp_d (x, 0) == MP_LT) {
  79     mp_set (&q, 1);
  80     if ((res = mp_lshd (&q, um + 1)) != MP_OKAY)
  81       goto CLEANUP;
  82     if ((res = mp_add (x, &q, x)) != MP_OKAY)
  83       goto CLEANUP;
  84   }
  85
  86   /* Back off if it's too big */
  87   while (mp_cmp (x, m) != MP_LT) {
  88     if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
  89       goto CLEANUP;
  90     }
  91   }
  92
  93 CLEANUP:
  94   mp_clear (&q);
  95
  96   return res;
  97 }
  98 #endif
  99
 100 /* Source: /cvs/libtom/libtommath/bn_mp_reduce.c,v  */
 101 /* Revision: 1.4  */
 102 /* Date: 2006/12/28 01:25:13  */