Struct IndexCalculus 

struct IndexCalculus {
    primes: PrimeList,
    br_primes: Vec<BarrettReduction<u64>>,
    ic: HashMap<u64, IndexCalculusWithPrimitiveRoot>,
}

Fields

primes: PrimeList

br_primes: Vec<BarrettReduction<u64>>

ic: HashMap<u64, IndexCalculusWithPrimitiveRoot>

Implementations

impl IndexCalculus

fn new() -> Self

fn discrete_logarithm(&mut self, a: u64, b: u64, p: u64) -> Option<(u64, u64)>

Examples found in repository

crates/competitive/src/math/discrete_logarithm.rs (line 344)

pub fn discrete_logarithm_prime_mod(a: u64, b: u64, p: u64) -> Option<u64> {
    IC.with(|ic| unsafe { &mut *ic.get() }.discrete_logarithm(a, b, p))
        .map(|t| t.0)
}

/// a^x ≡ b (mod n), a has order p^e
fn pohlig_hellman_prime_power_order(a: u64, b: u64, n: u64, p: u64, e: u32) -> Option<u64> {
    let br = BarrettReduction::<u128>::new(n as u128);
    let mul = |x: u64, y: u64| br.rem(x as u128 * y as u128) as u64;
    let block_size = (p as f64).sqrt().ceil() as u64;
    let mut baby = HashMap::<u64, u64>::new();
    let g = pow(a, p.pow(e - 1), &br);
    let mut xj = 1;
    for j in 0..block_size {
        baby.entry(xj).or_insert(j);
        xj = mul(xj, g);
    }
    let xi = modinv(xj, n);
    let mut t = 0u64;
    for k in 0..e {
        let mut h = pow(mul(modinv(pow(a, t, &br), n), b), p.pow(e - 1 - k), &br);
        let mut ok = false;
        for i in (0..block_size * block_size).step_by(block_size as usize) {
            if let Some(j) = baby.get(&h) {
                t += (i + j) * p.pow(k);
                ok = true;
                break;
            }
            h = mul(h, xi);
        }
        if !ok {
            return None;
        }
    }
    Some(t)
}

/// a^x ≡ b (mod p^e)
fn discrete_logarithm_prime_power(a: u64, b: u64, p: u64, e: u32) -> Option<(u64, u64)> {
    assert_ne!(p, 0);
    assert_ne!(e, 0);
    let n = p.pow(e);
    assert!(a < n);
    assert!(b < n);
    assert_eq!(gcd(a, p), 1);
    if p == 1 {
        return Some((0, 1));
    }
    if a == 0 {
        return if b == 0 { Some((1, 1)) } else { None };
    }
    if b == 0 {
        return None;
    }
    if e == 1 {
        return IC.with(|ic| unsafe { &mut *ic.get() }.discrete_logarithm(a, b, p));
    }
    let br = BarrettReduction::<u128>::new(n as _);
    if p == 2 {
        if e >= 3 {
            if a % 4 == 1 && b % 4 != 1 {
                return None;
            }
            let aa = if a % 4 == 1 { a } else { n - a };
            let bb = if b % 4 == 1 { b } else { n - b };
            let g = 5;
            let ord = n / 4;
            let x = pohlig_hellman_prime_power_order(g, aa, n, p, e - 2)?;
            let y = pohlig_hellman_prime_power_order(g, bb, n, p, e - 2)?;
            let t = solve_linear_congruence(x, y, ord)?;
            match (a % 4 == 1, b % 4 == 1) {
                (true, true) => Some(t),
                (false, true) if t.0 % 2 == 0 => Some((t.0, lcm(t.1, 2))),
                (false, false) if t.0 % 2 == 1 => Some((t.0, lcm(t.1, 2))),
                (false, false) if a == b => Some((1, lcm(t.1, 2))),
                _ => None,
            }
        } else if a == 1 {
            if b == 1 { Some((0, 1)) } else { None }
        } else {
            assert_eq!(a, 3);
            if b == 1 {
                Some((0, 2))
            } else if b == 3 {
                Some((1, 2))
            } else {
                None
            }
        }
    } else {
        let ord = n - n / p;
        let pf_ord = prime_factors(ord);
        let g = (2..)
            .find(|&g| check_primitive_root(g, ord, &br, &pf_ord))
            .unwrap();
        let mut pf_p = prime_factors(p - 1);
        pf_p.push((p, e - 1));
        let mut abm = vec![];
        for (q, c) in pf_p {
            let m = q.pow(c);
            let d = ord / m;
            let gg = pow(g, d, &br);
            let aa = pow(a, d, &br);
            let bb = pow(b, d, &br);
            let x = pohlig_hellman_prime_power_order(gg, aa, n, q, c)?;
            let y = pohlig_hellman_prime_power_order(gg, bb, n, q, c)?;
            abm.push((x, y, m));
        }
        solve_linear_congruences(abm)
    }
}

Trait Implementations

impl Debug for IndexCalculus

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.