fn solve_linear_congruences<I>(abm: I) -> Option<(u64, u64)>Examples found in repository?
crates/competitive/src/math/discrete_logarithm.rs (line 451)
381fn discrete_logarithm_prime_power(a: u64, b: u64, p: u64, e: u32) -> Option<(u64, u64)> {
382 assert_ne!(p, 0);
383 assert_ne!(e, 0);
384 let n = p.pow(e);
385 assert!(a < n);
386 assert!(b < n);
387 assert_eq!(gcd(a, p), 1);
388 if p == 1 {
389 return Some((0, 1));
390 }
391 if a == 0 {
392 return if b == 0 { Some((1, 1)) } else { None };
393 }
394 if b == 0 {
395 return None;
396 }
397 if e == 1 {
398 return IC.with(|ic| unsafe { &mut *ic.get() }.discrete_logarithm(a, b, p));
399 }
400 let br = BarrettReduction::<u128>::new(n as _);
401 if p == 2 {
402 if e >= 3 {
403 if a % 4 == 1 && b % 4 != 1 {
404 return None;
405 }
406 let aa = if a % 4 == 1 { a } else { n - a };
407 let bb = if b % 4 == 1 { b } else { n - b };
408 let g = 5;
409 let ord = n / 4;
410 let x = pohlig_hellman_prime_power_order(g, aa, n, p, e - 2)?;
411 let y = pohlig_hellman_prime_power_order(g, bb, n, p, e - 2)?;
412 let t = solve_linear_congruence(x, y, ord)?;
413 match (a % 4 == 1, b % 4 == 1) {
414 (true, true) => Some(t),
415 (false, true) if t.0 % 2 == 0 => Some((t.0, lcm(t.1, 2))),
416 (false, false) if t.0 % 2 == 1 => Some((t.0, lcm(t.1, 2))),
417 (false, false) if a == b => Some((1, lcm(t.1, 2))),
418 _ => None,
419 }
420 } else if a == 1 {
421 if b == 1 { Some((0, 1)) } else { None }
422 } else {
423 assert_eq!(a, 3);
424 if b == 1 {
425 Some((0, 2))
426 } else if b == 3 {
427 Some((1, 2))
428 } else {
429 None
430 }
431 }
432 } else {
433 let ord = n - n / p;
434 let pf_ord = prime_factors(ord);
435 let g = (2..)
436 .find(|&g| check_primitive_root(g, ord, &br, &pf_ord))
437 .unwrap();
438 let mut pf_p = prime_factors(p - 1);
439 pf_p.push((p, e - 1));
440 let mut abm = vec![];
441 for (q, c) in pf_p {
442 let m = q.pow(c);
443 let d = ord / m;
444 let gg = pow(g, d, &br);
445 let aa = pow(a, d, &br);
446 let bb = pow(b, d, &br);
447 let x = pohlig_hellman_prime_power_order(gg, aa, n, q, c)?;
448 let y = pohlig_hellman_prime_power_order(gg, bb, n, q, c)?;
449 abm.push((x, y, m));
450 }
451 solve_linear_congruences(abm)
452 }
453}
454
455/// a^x ≡ b (mod n)
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}