fn discrete_logarithm_prime_power(
a: u64,
b: u64,
p: u64,
e: u32,
) -> Option<(u64, u64)>Expand description
a^x ≡ b (mod p^e)
Examples found in repository?
crates/competitive/src/math/discrete_logarithm.rs (line 475)
454pub fn discrete_logarithm(a: u64, b: u64, n: u64) -> Option<u64> {
455 let a = a % n;
456 let b = b % n;
457 let d = 2.max(64 - n.leading_zeros() as u64);
458 let mut pw = 1 % n;
459 for i in 0..d {
460 if pw == b {
461 return Some(i);
462 }
463 pw = (pw as u128 * a as u128 % n as u128) as u64;
464 }
465 let g = gcd(pw, n);
466 if !b.is_multiple_of(g) {
467 return None;
468 }
469 let n = n / g;
470 let b = (b as u128 * modinv(pw, n) as u128 % n as u128) as u64;
471 let pf = prime_factors(n);
472 let mut abm = vec![];
473 for (p, e) in pf {
474 let q = p.pow(e);
475 let x = discrete_logarithm_prime_power(a % q, b % q, p, e)?;
476 abm.push((1, x.0, x.1));
477 }
478 solve_linear_congruences(abm).map(|x| x.0 + d)
479}