Rust functions of Chinese Remainder Theorem.

crt.rs

/// Find values where satisify `a * p + b * q = gcd`.
pub fn ext_gcd(a: u64, b: u64) -> ExtGcd {
    let mut s = (0i64, 1i64);
    let mut t = (1i64, 0i64);
    let mut r = (as_i64(b), as_i64(a));

    while r.0 != 0 {
        let q = r.1 / r.0;
        let f = |mut r: (i64, i64)| {
            std::mem::swap(&mut r.0, &mut r.1);
            r.0 -= q * r.1;
            r
        };
        r = f(r);
        s = f(s);
        t = f(t);
    }
    if 0 <= r.1 {
        ExtGcd {
            p: s.1,
            q: t.1,
            gcd: r.1 as u64,
        }
    } else {
        ExtGcd {
            p: -s.1,
            q: -t.1,
            gcd: -r.1 as u64,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct ExtGcd {
    pub p: i64,
    pub q: i64,
    pub gcd: u64,
}

/// Finds `x ≡ r (mod lcm(m1, m2))` where `x ≡ r1 (mod m1), x ≡ r2 (mod m2)`,
/// then returns `(x, lcm(m1, m2))` if exists.
pub fn chinese_rem(r1: u64, m1: u64, r2: u64, m2: u64) -> Option<(u64, u64)> {
    let ExtGcd { p, gcd, .. } = ext_gcd(m1, m2);
    let diff = r1.abs_diff(r2);
    if diff % gcd != 0 {
        return None;
    }
    let lcm = m2 / gcd * m1;
    let tmp = as_i64(diff) / as_i64(gcd) * p % (as_i64(m2) / as_i64(gcd));
    let rem = (as_i64(r1) + as_i64(m1) * tmp).rem_euclid(as_i64(lcm));
    Some((rem.try_into().unwrap(), lcm))
}

fn as_i64(x: u64) -> i64 {
    x.try_into().unwrap()
}

#[test]
fn verify() {
    assert_eq!(ext_gcd(15, 20), ExtGcd { p: -1, q: 1, gcd: 5 });
    // x ≡ 2 (mod 3)
    // x ≡ 3 (mod 5)
    //
    // should be:
    //
    // x ≡ 8 (mod 15)
    assert_eq!(chinese_rem(2, 3, 3, 5), Some((8, 15)));
}