Trait nekolib::math::mod_ord::ModOrd

pub trait ModOrd: Sized {
    // Required method
    fn mod_ord(self, other: Self) -> Option<Self>;
}

Expand description

位数。

法を $n$ として $a, a^2, \dots, a^m$ が互いに異なり、かつ $a^m \equiv 1$ である $m$ が存在すれば、それを返す。

$0\le a\lt n$ とする。

Complexity

$\lambda(n)$ に対する素因数列挙にかかる時間に加え、各素因数に対して $O(\log(\lambda(n)))$ 時間。試し割り法では $O(\sqrt{n})$ 時間。

use nekolib::math::ModOrd;

assert_eq!(7_u64.mod_ord(10), Some(4));
assert_eq!(1_u64.mod_ord(3), Some(1));
assert_eq!(22_u64.mod_ord(30), None);

dlog と同様、 $\lambda$ 関数と素因数列挙に関して引数で渡したいかも。