Trait nekolib::math::CarmichaelLambda

pub trait CarmichaelLambda {
    // Required method
    fn carmichael_lambda(self) -> Self;
}

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);

Required Methods

fn carmichael_lambda(self) -> Self

Implementations on Foreign Types

impl CarmichaelLambda for u32

fn carmichael_lambda(self) -> Self

impl CarmichaelLambda for u8

fn carmichael_lambda(self) -> Self

impl CarmichaelLambda for u16

fn carmichael_lambda(self) -> Self

impl CarmichaelLambda for u128

fn carmichael_lambda(self) -> Self

impl CarmichaelLambda for u64

fn carmichael_lambda(self) -> Self

impl CarmichaelLambda for usize

fn carmichael_lambda(self) -> Self

Implementors