Pollard's rho algorithm for logarithms in Rust.

discrete_log.rs

/// Finds `x` where `alpha` ** `x` == `beta`.
pub fn discrete_log<const MOD_1: u64, const MOD: u64>(alpha: ModInt<MOD>, beta: ModInt<MOD>) -> Option<u64> {
    assert_eq!(MOD_1 + 1, MOD);
    fn step<const MOD_1: u64, const MOD: u64>(alpha: ModInt<MOD>, beta: ModInt<MOD>, x: &mut ModInt<MOD>, a: &mut ModInt<MOD_1>, b: &mut ModInt<MOD_1>) {
        match x.as_u64() % 3 {
            0 => {
                *x = *x * *x;
                *a = *a * 2.into();
                *b = *b * 2.into();
            }
            1 => {
                *x = *x * alpha;
                *a = *a + 1.into();
            }
            2 => {
                *x = *x * beta;
                *b = *b + 1.into();
            }
            _ => unreachable!(),
        }
    }
    // find a, b, a2, b2 where α^a * β^b = α^a2 * β^b2
    let (mut x, mut a, mut b) = (1.into(), 0.into(), 0.into());
    let (mut x2, mut a2, mut b2) = (1.into(), 0.into(), 0.into());
    for _ in 0..MOD {
        step::<MOD_1, MOD>(alpha, beta, &mut x, &mut a, &mut b);
        step::<MOD_1, MOD>(alpha, beta, &mut x2, &mut a2, &mut b2);
        step::<MOD_1, MOD>(alpha, beta, &mut x2, &mut a2, &mut b2);
        if x == x2 {
            let r = (b2 - b).as_u64();
            if r == 0 {
                return None;
            }
            let x = (a - a2).as_u64() / r;
            return Some(x);
        }
    }
    None
}

#[test]
fn test_log() {
    assert_eq!(discrete_log::<1018, 1019>(2.into(), 5.into()), 10.into());
}
    
// ModInt is here: https://gist.github.com/MikuroXina/e590a0729b5d00ea6450c74733d2b5c4/