Tree @debian/0.061-1 (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_exptmod.c @debian/0.061-1 — 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 | #include "tommath_private.h" #ifdef BN_MP_EXPTMOD_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. */ /* this is a shell function that calls either the normal or Montgomery * exptmod functions. Originally the call to the montgomery code was * embedded in the normal function but that wasted alot of stack space * for nothing (since 99% of the time the Montgomery code would be called) */ int mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y) { int dr; /* modulus P must be positive */ if (P->sign == MP_NEG) { return MP_VAL; } /* if exponent X is negative we have to recurse */ if (X->sign == MP_NEG) { #ifdef BN_MP_INVMOD_C mp_int tmpG, tmpX; int err; /* first compute 1/G mod P */ if ((err = mp_init(&tmpG)) != MP_OKAY) { return err; } if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) { mp_clear(&tmpG); return err; } /* now get |X| */ if ((err = mp_init(&tmpX)) != MP_OKAY) { mp_clear(&tmpG); return err; } if ((err = mp_abs(X, &tmpX)) != MP_OKAY) { mp_clear_multi(&tmpG, &tmpX, NULL); return err; } /* and now compute (1/G)**|X| instead of G**X [X < 0] */ err = mp_exptmod(&tmpG, &tmpX, P, Y); mp_clear_multi(&tmpG, &tmpX, NULL); return err; #else /* no invmod */ return MP_VAL; #endif } /* modified diminished radix reduction */ #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C) if (mp_reduce_is_2k_l(P) == MP_YES) { return s_mp_exptmod(G, X, P, Y, 1); } #endif #ifdef BN_MP_DR_IS_MODULUS_C /* is it a DR modulus? */ dr = mp_dr_is_modulus(P); #else /* default to no */ dr = 0; #endif #ifdef BN_MP_REDUCE_IS_2K_C /* if not, is it a unrestricted DR modulus? */ if (dr == 0) { dr = mp_reduce_is_2k(P) << 1; } #endif /* if the modulus is odd or dr != 0 use the montgomery method */ #ifdef BN_MP_EXPTMOD_FAST_C if ((mp_isodd(P) == MP_YES) || (dr != 0)) { return mp_exptmod_fast(G, X, P, Y, dr); } else { #endif #ifdef BN_S_MP_EXPTMOD_C /* otherwise use the generic Barrett reduction technique */ return s_mp_exptmod(G, X, P, Y, 0); #else /* no exptmod for evens */ return MP_VAL; #endif #ifdef BN_MP_EXPTMOD_FAST_C } #endif } #endif /* ref: $Format:%D$ */ /* git commit: $Format:%H$ */ /* commit time: $Format:%ai$ */ |