nekolib/math/
carmichael_lambda.rs

1//! Carmichael の $\\lambda$ 関数。
2
3use super::factors;
4use super::lcm;
5
6use factors::Factors;
7use lcm::Lcm;
8
9/// Carmichael の $\\lambda$ 関数。
10///
11/// $\\lambda(n)$ は、$\\gcd(a, n)$ である任意の $a$ に対して
12/// $a^m\\equiv 1 \\pmod{n}$ となる最小の $m$ として定義される。
13///
14/// $\\gdef\\lcm{\\operatorname\*{lcm}}$
15/// 以下の式によって計算される。
16/// - $\\lambda(1) = 1$
17/// - $\\lambda(2) = 1$
18/// - $\\lambda(4) = 2$
19/// - $\\lambda(2^e) = 2^{e-2}$ for $e\\ge 3$
20/// - $\\lambda(p^e) = \\varphi(p^e) = p^{e-1}(p-1)$ for odd prime $p$
21/// - $\\lambda(\\prod\_{p:\\text{ prime}} p\_i^{e\_i}) = \\lcm\_i \\lambda(p\_i^{e\_i})$
22///
23/// # Complexity
24/// $O(\\sqrt{n})$ time.
25///
26/// # Examples
27/// ```
28/// use nekolib::math::CarmichaelLambda;
29///
30/// assert_eq!(1_u64.carmichael_lambda(), 1);
31/// assert_eq!(15_u64.carmichael_lambda(), 4);
32/// assert_eq!(21_u64.carmichael_lambda(), 6);
33/// assert_eq!(33_u64.carmichael_lambda(), 10);
34/// ```
35pub trait CarmichaelLambda {
36    fn carmichael_lambda(self) -> Self;
37}
38
39macro_rules! impl_uint {
40    ($t:ty) => {
41        impl CarmichaelLambda for $t {
42            fn carmichael_lambda(self) -> Self {
43                let n = self;
44                let e2 = n.trailing_zeros() as $t;
45                let mut res = match e2 {
46                    0 | 1 => 1,
47                    2 => 2,
48                    _ => 1 << (e2 - 2),
49                };
50                for (p, e) in (n >> e2).factors() {
51                    res = res.lcm(p.pow(e - 1) * (p - 1));
52                }
53                res
54            }
55        }
56    };
57    ( $($t:ty)* ) => { $(impl_uint!($t);)* };
58}
59
60impl_uint!(u8 u16 u32 u64 u128 usize);
61
62#[test]
63fn test() {
64    use gcd::Gcd;
65
66    let n_max = 1000_usize;
67    assert_eq!(1_usize.carmichael_lambda(), 1);
68    for n in 2..=n_max {
69        let mut pow = vec![1; n];
70        let relp: Vec<_> = (0..n).filter(|&a| a.gcd(n) == 1).collect();
71        for e in 1..n {
72            for &a in &relp {
73                pow[a] = pow[a] * a % n;
74            }
75            if pow.iter().all(|&x| x == 1) {
76                assert_eq!(
77                    n.carmichael_lambda(),
78                    e,
79                    "lambda({}) = {}? {}",
80                    n,
81                    e,
82                    n.carmichael_lambda()
83                );
84                break;
85            }
86        }
87        assert!(pow.iter().all(|&x| x == 1));
88    }
89}
nekolib/math/carmichael_lambda.rs

nekolib/math/
carmichael_lambda.rs
