Solve (N * K) mod 2^64 = 1

mod_eqn_solver.rs

// for given number N, this function finds another number K such that
// (N * K) mod 2^64 = 1
fn mult_mod_inv(n: u64) -> u64 {
    assert!(n & 1 == 1, "Doesnt work for even numbers");
    assert!(n != 0, "Equation 0 mod N == 1 does not have a solution");
    let mut k = 1u64;
    let mut i = 1u64;
    for _ in 0 .. 64 {
        i <<= 1;
        let c = k.wrapping_mul(n);
        if c & i != 0 { k ^= i }
    }

    return k;
}

#[test]
fn t14() {
    let d = 9;
    let k = mult_mod_inv(d);
    println!("{} {}", k, k.wrapping_mul(d)) // second value is 1
}