1 #include <tommath.h> 2 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4 * 5 * LibTomMath is a library that provides multiple-precision 6 * integer arithmetic as well as number theoretic functionality. 7 * 8 * The library was designed directly after the MPI library by 9 * Michael Fromberger but has been written from scratch with 10 * additional optimizations in place. 11 * 12 * The library is free for all purposes without any express 13 * guarantee it works. 14 * 15 * Tom St Denis, tomstdenis (at) gmail.com, http://math.libtomcrypt.com 16 */ 17 18 /* 19 * shifts with subtractions when the result is greater than b. 20 * 21 * The method is slightly modified to shift B unconditionally upto just under 22 * the leading bit of b. This saves alot of multiple precision shifting. 23 */ 24 int mp_montgomery_calc_normalization (mp_int * a, mp_int * b) 25 { 26 int x, bits, res; 27 28 /* how many bits of last digit does b use */ 29 bits = mp_count_bits (b) % DIGIT_BIT; 30 31 if (b->used > 1) { 32 if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) { 33 return res; 34 } 35 } else { 36 mp_set(a, 1); 37 bits = 1; 38 } 39 40 41 /* now compute C = A * B mod b */ 42 for (x = bits - 1; x < (int)DIGIT_BIT; x++) { 43 if ((res = mp_mul_2 (a, a)) != MP_OKAY) { 44 return res; 45 } 46 if (mp_cmp_mag (a, b) != MP_LT) { 47 if ((res = s_mp_sub (a, b, a)) != MP_OKAY) { 48 return res; 49 } 50 } 51 } 52 53 return MP_OKAY; 54 } 55 #endif 56 57 /* $Source: /cvs/libtom/libtommath/bn_mp_montgomery_calc_normalization.c,v $ */ 58 /* $Revision: 1.3 $ */ 59 /* $Date: 2006/03/31 14:18:44 $ */ 60
