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 477)
456pub fn discrete_logarithm(a: u64, b: u64, n: u64) -> Option<u64> {
457 let a = a % n;
458 let b = b % n;
459 let d = 2.max(64 - n.leading_zeros() as u64);
460 let mut pw = 1 % n;
461 for i in 0..d {
462 if pw == b {
463 return Some(i);
464 }
465 pw = (pw as u128 * a as u128 % n as u128) as u64;
466 }
467 let g = gcd(pw, n);
468 if !b.is_multiple_of(g) {
469 return None;
470 }
471 let n = n / g;
472 let b = (b as u128 * modinv(pw, n) as u128 % n as u128) as u64;
473 let pf = prime_factors(n);
474 let mut abm = vec![];
475 for (p, e) in pf {
476 let q = p.pow(e);
477 let x = discrete_logarithm_prime_power(a % q, b % q, p, e)?;
478 abm.push((1, x.0, x.1));
479 }
480 solve_linear_congruences(abm).map(|x| x.0 + d)
481}