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_exteuclid.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 | #include "tommath_private.h" #ifdef BN_MP_EXTEUCLID_C /* LibTomMath, multiple-precision integer library -- Tom St Denis */ /* SPDX-License-Identifier: Unlicense */ /* Extended euclidean algorithm of (a, b) produces a*u1 + b*u2 = u3 */ mp_err mp_exteuclid(const mp_int *a, const mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3) { mp_int u1, u2, u3, v1, v2, v3, t1, t2, t3, q, tmp; mp_err err; if ((err = mp_init_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL)) != MP_OKAY) { return err; } /* initialize, (u1,u2,u3) = (1,0,a) */ mp_set(&u1, 1uL); if ((err = mp_copy(a, &u3)) != MP_OKAY) { goto LBL_ERR; } /* initialize, (v1,v2,v3) = (0,1,b) */ mp_set(&v2, 1uL); if ((err = mp_copy(b, &v3)) != MP_OKAY) { goto LBL_ERR; } /* loop while v3 != 0 */ while (!MP_IS_ZERO(&v3)) { /* q = u3/v3 */ if ((err = mp_div(&u3, &v3, &q, NULL)) != MP_OKAY) { goto LBL_ERR; } /* (t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q */ if ((err = mp_mul(&v1, &q, &tmp)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_sub(&u1, &tmp, &t1)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_mul(&v2, &q, &tmp)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_sub(&u2, &tmp, &t2)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_mul(&v3, &q, &tmp)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_sub(&u3, &tmp, &t3)) != MP_OKAY) { goto LBL_ERR; } /* (u1,u2,u3) = (v1,v2,v3) */ if ((err = mp_copy(&v1, &u1)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_copy(&v2, &u2)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_copy(&v3, &u3)) != MP_OKAY) { goto LBL_ERR; } /* (v1,v2,v3) = (t1,t2,t3) */ if ((err = mp_copy(&t1, &v1)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_copy(&t2, &v2)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_copy(&t3, &v3)) != MP_OKAY) { goto LBL_ERR; } } /* make sure U3 >= 0 */ if (u3.sign == MP_NEG) { if ((err = mp_neg(&u1, &u1)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_neg(&u2, &u2)) != MP_OKAY) { goto LBL_ERR; } if ((err = mp_neg(&u3, &u3)) != MP_OKAY) { goto LBL_ERR; } } /* copy result out */ if (U1 != NULL) { mp_exch(U1, &u1); } if (U2 != NULL) { mp_exch(U2, &u2); } if (U3 != NULL) { mp_exch(U3, &u3); } err = MP_OKAY; LBL_ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL); return err; } #endif |