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})$ 時間。
Examples
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);Suggestions
dlog と同様、$\lambda$ 関数と素因数列挙に関して引数で渡したいかも。