haar_lib/math/mod_ops/
log.rs

1//! aˣ = b (mod m)を満たすxを求める。
2
3use crate::math::{
4    gcd_lcm::GcdLcm,
5    mod_ops::{inv::*, pow::*},
6};
7use std::collections::HashMap;
8
9/// aˣ = b (mod m)を満たすxを求める。
10///
11/// **Time complexity** $O(\sqrt{m})$
12pub fn mod_log(a: u64, mut b: u64, mut m: u64) -> Option<u64> {
13    if b == 1 {
14        return Some(0);
15    }
16
17    let mut d = 0;
18
19    loop {
20        let g = a.gcd(m);
21        if g != 1 {
22            if b % g != 0 {
23                return None;
24            }
25
26            d += 1;
27            m /= g;
28            b /= g;
29            b *= mod_inv(a / g, m).unwrap();
30            b %= m;
31
32            if b == 1 {
33                return Some(d);
34            }
35        } else {
36            break;
37        }
38    }
39
40    let sq = (m as f64).sqrt() as u64 + 1;
41
42    let mut mp = HashMap::new();
43
44    let mut t = 1 % m;
45
46    for i in 0..sq {
47        mp.entry(t).or_insert(i);
48        t *= a;
49        t %= m;
50    }
51
52    let x = mod_pow(mod_inv(a, m).unwrap(), sq, m);
53    let mut t = b % m;
54
55    for i in 0..sq {
56        if let Some(k) = mp.get(&t) {
57            return Some(i * sq + k + d);
58        }
59
60        t *= x;
61        t %= m;
62    }
63
64    None
65}
haar_lib/math/mod_ops/log.rs

haar_lib/math/mod_ops/
log.rs
