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_prime_miller_rabin.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 | #include "tommath_private.h" #ifdef BN_MP_PRIME_MILLER_RABIN_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. */ /* Miller-Rabin test of "a" to the base of "b" as described in * HAC pp. 139 Algorithm 4.24 * * Sets result to 0 if definitely composite or 1 if probably prime. * Randomly the chance of error is no more than 1/4 and often * very much lower. */ int mp_prime_miller_rabin(const mp_int *a, const mp_int *b, int *result) { mp_int n1, y, r; int s, j, err; /* default */ *result = MP_NO; /* ensure b > 1 */ if (mp_cmp_d(b, 1uL) != MP_GT) { return MP_VAL; } /* get n1 = a - 1 */ if ((err = mp_init_copy(&n1, a)) != MP_OKAY) { return err; } if ((err = mp_sub_d(&n1, 1uL, &n1)) != MP_OKAY) { goto LBL_N1; } /* set 2**s * r = n1 */ if ((err = mp_init_copy(&r, &n1)) != MP_OKAY) { goto LBL_N1; } /* count the number of least significant bits * which are zero */ s = mp_cnt_lsb(&r); /* now divide n - 1 by 2**s */ if ((err = mp_div_2d(&r, s, &r, NULL)) != MP_OKAY) { goto LBL_R; } /* compute y = b**r mod a */ if ((err = mp_init(&y)) != MP_OKAY) { goto LBL_R; } if ((err = mp_exptmod(b, &r, a, &y)) != MP_OKAY) { goto LBL_Y; } /* if y != 1 and y != n1 do */ if ((mp_cmp_d(&y, 1uL) != MP_EQ) && (mp_cmp(&y, &n1) != MP_EQ)) { j = 1; /* while j <= s-1 and y != n1 */ while ((j <= (s - 1)) && (mp_cmp(&y, &n1) != MP_EQ)) { if ((err = mp_sqrmod(&y, a, &y)) != MP_OKAY) { goto LBL_Y; } /* if y == 1 then composite */ if (mp_cmp_d(&y, 1uL) == MP_EQ) { goto LBL_Y; } ++j; } /* if y != n1 then composite */ if (mp_cmp(&y, &n1) != MP_EQ) { goto LBL_Y; } } /* probably prime now */ *result = MP_YES; LBL_Y: mp_clear(&y); LBL_R: mp_clear(&r); LBL_N1: mp_clear(&n1); return err; } #endif /* ref: $Format:%D$ */ /* git commit: $Format:%H$ */ /* commit time: $Format:%ai$ */ |