fn extended_binary_gcd()

in crypto/src/gcd.rs [10:78]

• 55 lines of code
• 10 McCabe index (conditional complexity)

fn extended_binary_gcd(m: &BigUint, n: &BigUint) -> (BigInt, BigInt, BigUint) {
    #[inline]
    fn count_twos_multiple(x: &BigUint) -> u64 {
        x.trailing_zeros().unwrap_or(0)
    }

    // Assume non zero
    assert!(!m.is_zero());
    assert!(!n.is_zero());

    let mut x_ebgcd = m.clone();
    let mut y_ebgcd = n.clone();
    let mut g_ebgcd = BigUint::one();

    // find common factors of 2
    let shift = cmp::min(count_twos_multiple(&x_ebgcd), count_twos_multiple(&y_ebgcd));

    x_ebgcd >>= shift;
    y_ebgcd >>= shift;
    g_ebgcd <<= shift;

    let mut u_ebgcd = x_ebgcd.clone();
    let mut v_ebgcd = y_ebgcd.clone();

    let mut a_ebgcd = BigInt::one();
    let mut b_ebgcd = BigInt::zero();
    let mut c_ebgcd = BigInt::zero();
    let mut d_ebgcd = BigInt::one();

    loop {
        while u_ebgcd.is_even() {
            u_ebgcd >>= 1;

            if a_ebgcd.is_even() && b_ebgcd.is_even() {
                a_ebgcd >>= 1;
                b_ebgcd >>= 1;
            } else {
                a_ebgcd = (a_ebgcd + y_ebgcd.to_bigint().unwrap()) >> 1;
                b_ebgcd = (b_ebgcd - x_ebgcd.to_bigint().unwrap()) >> 1;
            }
        }

        while v_ebgcd.is_even() {
            v_ebgcd >>= 1;

            if c_ebgcd.is_even() && d_ebgcd.is_even() {
                c_ebgcd >>= 1;
                d_ebgcd >>= 1;
            } else {
                c_ebgcd = (c_ebgcd + y_ebgcd.to_bigint().unwrap()) >> 1;
                d_ebgcd = (d_ebgcd - x_ebgcd.to_bigint().unwrap()) >> 1;
            }
        }

        if u_ebgcd >= v_ebgcd {
            u_ebgcd -= &v_ebgcd;
            a_ebgcd -= &c_ebgcd;
            b_ebgcd -= &d_ebgcd;
        } else {
            v_ebgcd -= &u_ebgcd;
            c_ebgcd -= &a_ebgcd;
            d_ebgcd -= &b_ebgcd;
        }

        if u_ebgcd.is_zero() {
            return (c_ebgcd.clone(), d_ebgcd.clone(), v_ebgcd << shift);
        }
    }
}