Trait nekolib::math::CarmichaelLambda
source · pub trait CarmichaelLambda {
// Required method
fn carmichael_lambda(self) -> Self;
}Expand description
Carmichael の $\lambda$ 関数。
$\lambda(n)$ は、$\gcd(a, n)$ である任意の $a$ に対して $a^m\equiv 1 \pmod{n}$ となる最小の $m$ として定義される。
$\gdef{\lcm}{\operatorname*{lcm}}$ 以下の式によって計算される。
- $\lambda(1) = 1$
- $\lambda(2) = 1$
- $\lambda(4) = 2$
- $\lambda(2^e) = 2^{e-2}$ for $e\ge 3$
- $\lambda(p^e) = \varphi(p^e) = p^{e-1}(p-1)$ for odd prime $p$
- $\lambda(\prod_{p:\text{ prime}} p_i^{e_i}) = \lcm_i \lambda(p_i^{e_i})$
Complexity
$O(\sqrt{n})$ time.
Examples
use nekolib::math::CarmichaelLambda;
assert_eq!(1_u64.carmichael_lambda(), 1);
assert_eq!(15_u64.carmichael_lambda(), 4);
assert_eq!(21_u64.carmichael_lambda(), 6);
assert_eq!(33_u64.carmichael_lambda(), 10);