GCD useful for RSA & Quantum (CSCA 5454)

gcd_alt.rs

fn gcd1(mut m: i32, mut n: i32) -> i32 {
    let mut t = 0;
    while n != 0 {
        t = n;
        n = m % n;
        m = t;
    }
    m
}

gcd_euler_totient.rs

fn gcd(mut m: i32, mut n: i32) -> (i32, i32, i32) {
    assert!(m >= 1 && n >= 0 && m >= n);

    let m0 = m;
    let n0 = n;
    let (mut s, mut t) = (1, 0);
    let (mut s_hat, mut t_hat) = (0, 1);

    while n > 0 {
        assert_eq!(m, s * m0 + t * n0);
        assert_eq!(n, s_hat * m0 + t_hat * n0);
        let q = m / n;
        let r = m % n;
        let (a, b) = (s - q * s_hat, t - q * t_hat);
        (m, n, s, t, s_hat, t_hat) = (n, r, s_hat, t_hat, a, b);
        
        println!("GCD({}, {}) = GCD({}, {})", m0, n0, m, n);
        println!("\t {} = {}*{} + {}*{}", m, s, m0, t, n0);
        println!("\t {} = {}*{} + {}*{}", n, s_hat, m0, t_hat, n0);
    }

    (m, s, t)
}

fn totient(n: i32) -> usize {
    (1..n)
        .filter(|m| {
            let (res, _, _) = gcd(n, *m);
            res == 1
        })
        .collect::<Vec<_>>()
        .len()
}

order_find.rs

fn order(i: i32, m: i32) -> i32 {
    if gcd1(i, m) != 1 { return -1; }
    
    let mut pow = 1;
    for k in 1..m {
        pow = (i * pow) % m;
        if pow == 1 {
            return k;
        }
    }
    -1
}