Tree @f21e5f2 (Download .tar.gz)
- ..
- bn_cutoffs.c
- bn_deprecated.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_complement.c
- bn_mp_copy.c
- bn_mp_count_bits.c
- bn_mp_decr.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_error_to_string.c
- bn_mp_exch.c
- bn_mp_export.c
- bn_mp_expt_d.c
- bn_mp_exptmod.c
- bn_mp_exteuclid.c
- bn_mp_fread.c
- bn_mp_fwrite.c
- bn_mp_gcd.c
- bn_mp_get_i32.c
- bn_mp_get_i64.c
- bn_mp_get_mag32.c
- bn_mp_get_mag64.c
- bn_mp_grow.c
- bn_mp_ilogb.c
- bn_mp_import.c
- bn_mp_incr.c
- bn_mp_init.c
- bn_mp_init_copy.c
- bn_mp_init_i32.c
- bn_mp_init_i64.c
- bn_mp_init_multi.c
- bn_mp_init_set.c
- bn_mp_init_size.c
- bn_mp_init_u32.c
- bn_mp_init_u64.c
- bn_mp_invmod.c
- bn_mp_is_square.c
- bn_mp_iseven.c
- bn_mp_isodd.c
- bn_mp_kronecker.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_neg.c
- bn_mp_or.c
- bn_mp_prime_fermat.c
- bn_mp_prime_frobenius_underwood.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_rand.c
- bn_mp_prime_strong_lucas_selfridge.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_i32.c
- bn_mp_set_i64.c
- bn_mp_set_u32.c
- bn_mp_set_u64.c
- bn_mp_shrink.c
- bn_mp_signed_bin_size.c
- bn_mp_signed_rsh.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_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_s_mp_add.c
- bn_s_mp_balance_mul.c
- bn_s_mp_exptmod.c
- bn_s_mp_exptmod_fast.c
- bn_s_mp_get_bit.c
- bn_s_mp_invmod_fast.c
- bn_s_mp_invmod_slow.c
- bn_s_mp_karatsuba_mul.c
- bn_s_mp_karatsuba_sqr.c
- bn_s_mp_montgomery_reduce_fast.c
- bn_s_mp_mul_digs.c
- bn_s_mp_mul_digs_fast.c
- bn_s_mp_mul_high_digs.c
- bn_s_mp_mul_high_digs_fast.c
- bn_s_mp_prime_is_divisible.c
- bn_s_mp_rand_jenkins.c
- bn_s_mp_rand_platform.c
- bn_s_mp_reverse.c
- bn_s_mp_sqr.c
- bn_s_mp_sqr_fast.c
- bn_s_mp_sub.c
- bn_s_mp_toom_mul.c
- bn_s_mp_toom_sqr.c
- tommath.h
- tommath_class.h
- tommath_cutoffs.h
- tommath_private.h
- tommath_superclass.h
bn_mp_kronecker.c @f21e5f2 — 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 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include "tommath_private.h" #ifdef BN_MP_KRONECKER_C /* LibTomMath, multiple-precision integer library -- Tom St Denis */ /* SPDX-License-Identifier: Unlicense */ /* Kronecker symbol (a|p) Straightforward implementation of algorithm 1.4.10 in Henri Cohen: "A Course in Computational Algebraic Number Theory" @book{cohen2013course, title={A course in computational algebraic number theory}, author={Cohen, Henri}, volume={138}, year={2013}, publisher={Springer Science \& Business Media} } */ mp_err mp_kronecker(const mp_int *a, const mp_int *p, int *c) { mp_int a1, p1, r; mp_err err; int v, k; static const int table[8] = {0, 1, 0, -1, 0, -1, 0, 1}; if (MP_IS_ZERO(p)) { if ((a->used == 1) && (a->dp[0] == 1u)) { *c = 1; } else { *c = 0; } return MP_OKAY; } if (MP_IS_EVEN(a) && MP_IS_EVEN(p)) { *c = 0; return MP_OKAY; } if ((err = mp_init_copy(&a1, a)) != MP_OKAY) { return err; } if ((err = mp_init_copy(&p1, p)) != MP_OKAY) { goto LBL_KRON_0; } v = mp_cnt_lsb(&p1); if ((err = mp_div_2d(&p1, v, &p1, NULL)) != MP_OKAY) { goto LBL_KRON_1; } if ((v & 1) == 0) { k = 1; } else { k = table[a->dp[0] & 7u]; } if (p1.sign == MP_NEG) { p1.sign = MP_ZPOS; if (a1.sign == MP_NEG) { k = -k; } } if ((err = mp_init(&r)) != MP_OKAY) { goto LBL_KRON_1; } for (;;) { if (MP_IS_ZERO(&a1)) { if (mp_cmp_d(&p1, 1uL) == MP_EQ) { *c = k; goto LBL_KRON; } else { *c = 0; goto LBL_KRON; } } v = mp_cnt_lsb(&a1); if ((err = mp_div_2d(&a1, v, &a1, NULL)) != MP_OKAY) { goto LBL_KRON; } if ((v & 1) == 1) { k = k * table[p1.dp[0] & 7u]; } if (a1.sign == MP_NEG) { /* * Compute k = (-1)^((a1)*(p1-1)/4) * k * a1.dp[0] + 1 cannot overflow because the MSB * of the type mp_digit is not set by definition */ if (((a1.dp[0] + 1u) & p1.dp[0] & 2u) != 0u) { k = -k; } } else { /* compute k = (-1)^((a1-1)*(p1-1)/4) * k */ if ((a1.dp[0] & p1.dp[0] & 2u) != 0u) { k = -k; } } if ((err = mp_copy(&a1, &r)) != MP_OKAY) { goto LBL_KRON; } r.sign = MP_ZPOS; if ((err = mp_mod(&p1, &r, &a1)) != MP_OKAY) { goto LBL_KRON; } if ((err = mp_copy(&r, &p1)) != MP_OKAY) { goto LBL_KRON; } } LBL_KRON: mp_clear(&r); LBL_KRON_1: mp_clear(&p1); LBL_KRON_0: mp_clear(&a1); return err; } #endif |