Tree @831e872 (Download .tar.gz)
- ..
- bn_error.c
- bn_fast_mp_invmod.c
- bn_fast_mp_montgomery_reduce.c
- bn_fast_s_mp_mul_digs.c
- bn_fast_s_mp_mul_high_digs.c
- bn_fast_s_mp_sqr.c
- bn_mp_2expt.c
- bn_mp_abs.c
- bn_mp_add.c
- bn_mp_add_d.c
- bn_mp_addmod.c
- bn_mp_and.c
- bn_mp_clamp.c
- bn_mp_clear.c
- bn_mp_clear_multi.c
- bn_mp_cmp.c
- bn_mp_cmp_d.c
- bn_mp_cmp_mag.c
- bn_mp_cnt_lsb.c
- bn_mp_copy.c
- bn_mp_count_bits.c
- bn_mp_div.c
- bn_mp_div_2.c
- bn_mp_div_2d.c
- bn_mp_div_3.c
- bn_mp_div_d.c
- bn_mp_dr_is_modulus.c
- bn_mp_dr_reduce.c
- bn_mp_dr_setup.c
- bn_mp_exch.c
- bn_mp_export.c
- bn_mp_expt_d.c
- bn_mp_expt_d_ex.c
- bn_mp_exptmod.c
- bn_mp_exptmod_fast.c
- bn_mp_exteuclid.c
- bn_mp_fread.c
- bn_mp_fwrite.c
- bn_mp_gcd.c
- bn_mp_get_int.c
- bn_mp_get_long.c
- bn_mp_grow.c
- bn_mp_import.c
- bn_mp_init.c
- bn_mp_init_copy.c
- bn_mp_init_multi.c
- bn_mp_init_set.c
- bn_mp_init_set_int.c
- bn_mp_init_size.c
- bn_mp_invmod.c
- bn_mp_invmod_slow.c
- bn_mp_is_square.c
- bn_mp_jacobi.c
- bn_mp_karatsuba_mul.c
- bn_mp_karatsuba_sqr.c
- bn_mp_lcm.c
- bn_mp_lshd.c
- bn_mp_mod.c
- bn_mp_mod_2d.c
- bn_mp_mod_d.c
- bn_mp_montgomery_calc_normalization.c
- bn_mp_montgomery_reduce.c
- bn_mp_montgomery_setup.c
- bn_mp_mul.c
- bn_mp_mul_2.c
- bn_mp_mul_2d.c
- bn_mp_mul_d.c
- bn_mp_mulmod.c
- bn_mp_n_root.c
- bn_mp_n_root_ex.c
- bn_mp_neg.c
- bn_mp_or.c
- bn_mp_prime_fermat.c
- bn_mp_prime_is_divisible.c
- bn_mp_prime_is_prime.c
- bn_mp_prime_miller_rabin.c
- bn_mp_prime_next_prime.c
- bn_mp_prime_rabin_miller_trials.c
- bn_mp_prime_random_ex.c
- bn_mp_radix_size.c
- bn_mp_radix_smap.c
- bn_mp_rand.c
- bn_mp_read_radix.c
- bn_mp_read_signed_bin.c
- bn_mp_read_unsigned_bin.c
- bn_mp_reduce.c
- bn_mp_reduce_2k.c
- bn_mp_reduce_2k_l.c
- bn_mp_reduce_2k_setup.c
- bn_mp_reduce_2k_setup_l.c
- bn_mp_reduce_is_2k.c
- bn_mp_reduce_is_2k_l.c
- bn_mp_reduce_setup.c
- bn_mp_rshd.c
- bn_mp_set.c
- bn_mp_set_int.c
- bn_mp_set_long.c
- bn_mp_shrink.c
- bn_mp_signed_bin_size.c
- bn_mp_sqr.c
- bn_mp_sqrmod.c
- bn_mp_sqrt.c
- bn_mp_sqrtmod_prime.c
- bn_mp_sub.c
- bn_mp_sub_d.c
- bn_mp_submod.c
- bn_mp_to_signed_bin.c
- bn_mp_to_signed_bin_n.c
- bn_mp_to_unsigned_bin.c
- bn_mp_to_unsigned_bin_n.c
- bn_mp_toom_mul.c
- bn_mp_toom_sqr.c
- bn_mp_toradix.c
- bn_mp_toradix_n.c
- bn_mp_unsigned_bin_size.c
- bn_mp_xor.c
- bn_mp_zero.c
- bn_prime_tab.c
- bn_reverse.c
- bn_s_mp_add.c
- bn_s_mp_exptmod.c
- bn_s_mp_mul_digs.c
- bn_s_mp_mul_high_digs.c
- bn_s_mp_sqr.c
- bn_s_mp_sub.c
- bncore.c
- tommath.h
- tommath_class.h
- tommath_private.h
- tommath_superclass.h
bn_mp_montgomery_reduce.c @831e872 — raw · history · blame
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include "tommath_private.h" #ifdef BN_MP_MONTGOMERY_REDUCE_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * The library is free for all purposes without any express * guarantee it works. */ /* computes xR**-1 == x (mod N) via Montgomery Reduction */ int mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho) { int ix, res, digs; mp_digit mu; /* can the fast reduction [comba] method be used? * * Note that unlike in mul you're safely allowed *less* * than the available columns [255 per default] since carries * are fixed up in the inner loop. */ digs = (n->used * 2) + 1; if ((digs < (int)MP_WARRAY) && (x->used <= (int)MP_WARRAY) && (n->used < (int)(1u << (((size_t)CHAR_BIT * sizeof(mp_word)) - (2u * (size_t)DIGIT_BIT))))) { return fast_mp_montgomery_reduce(x, n, rho); } /* grow the input as required */ if (x->alloc < digs) { if ((res = mp_grow(x, digs)) != MP_OKAY) { return res; } } x->used = digs; for (ix = 0; ix < n->used; ix++) { /* mu = ai * rho mod b * * The value of rho must be precalculated via * montgomery_setup() such that * it equals -1/n0 mod b this allows the * following inner loop to reduce the * input one digit at a time */ mu = (mp_digit)(((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK); /* a = a + mu * m * b**i */ { int iy; mp_digit *tmpn, *tmpx, u; mp_word r; /* alias for digits of the modulus */ tmpn = n->dp; /* alias for the digits of x [the input] */ tmpx = x->dp + ix; /* set the carry to zero */ u = 0; /* Multiply and add in place */ for (iy = 0; iy < n->used; iy++) { /* compute product and sum */ r = ((mp_word)mu * (mp_word)*tmpn++) + (mp_word)u + (mp_word)*tmpx; /* get carry */ u = (mp_digit)(r >> (mp_word)DIGIT_BIT); /* fix digit */ *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK); } /* At this point the ix'th digit of x should be zero */ /* propagate carries upwards as required*/ while (u != 0u) { *tmpx += u; u = *tmpx >> DIGIT_BIT; *tmpx++ &= MP_MASK; } } } /* at this point the n.used'th least * significant digits of x are all zero * which means we can shift x to the * right by n.used digits and the * residue is unchanged. */ /* x = x/b**n.used */ mp_clamp(x); mp_rshd(x, n->used); /* if x >= n then x = x - n */ if (mp_cmp_mag(x, n) != MP_LT) { return s_mp_sub(x, n, x); } return MP_OKAY; } #endif /* ref: $Format:%D$ */ /* git commit: $Format:%H$ */ /* commit time: $Format:%ai$ */ |