nekolib/math/
mod_ord.rs

1//! 位数。
2
3use super::carmichael_lambda;
4use super::factors_dup;
5use super::gcd;
6use super::mod_pow;
7
8use carmichael_lambda::CarmichaelLambda;
9use factors_dup::FactorsDup;
10use gcd::Gcd;
11use mod_pow::ModPow;
12
13/// 位数。
14///
15/// 法を $n$ として $a, a^2, \\dots, a^m$ が互いに異なり、かつ $a^m \\equiv 1$ である
16/// $m$ が存在すれば、それを返す。
17///
18/// $0\\le a\\lt n$ とする。
19///
20/// # Complexity
21/// $\\lambda(n)$ に対する素因数列挙にかかる時間に加え、各素因数に対して
22/// $O(\\log(\\lambda(n)))$ 時間。試し割り法では $O(\\sqrt{n})$ 時間。
23///
24/// # Examples
25/// ```
26/// use nekolib::math::ModOrd;
27///
28/// assert_eq!(7_u64.mod_ord(10), Some(4));
29/// assert_eq!(1_u64.mod_ord(3), Some(1));
30/// assert_eq!(22_u64.mod_ord(30), None);
31/// ```
32///
33/// # Suggestions
34/// [`dlog`] と同様、$\\lambda$ 関数と素因数列挙に関して引数で渡したいかも。
35///
36/// [`dlog`]: fn.dlog.html
37pub trait ModOrd: Sized {
38    fn mod_ord(self, other: Self) -> Option<Self>;
39}
40
41macro_rules! impl_uint {
42    ($t:ty) => {
43        impl ModOrd for $t {
44            fn mod_ord(self, n: Self) -> Option<Self> {
45                assert_ne!(n, 0, "modulo must be positive");
46                let a = match self {
47                    0 => return None,
48                    1 => return Some(1),
49                    _ => self,
50                };
51
52                let g = a.gcd(n);
53                if g != 1 {
54                    return None;
55                }
56
57                let mut q = n.carmichael_lambda();
58                for e in q.factors_dup() {
59                    if a.mod_pow(q / e, n) == 1 {
60                        q /= e;
61                    }
62                }
63                (a.mod_pow(q, n) == 1).then(|| q)
64            }
65        }
66    };
67    ( $($t:ty)* ) => { $(impl_uint!($t);)* };
68}
69
70impl_uint!(u8 u16 u32 u64 u128 usize);
71
72#[test]
73fn test() {
74    let n_max = 500_u64;
75
76    for n in 2..=n_max {
77        for a in 0..n {
78            let actual = a.mod_ord(n);
79            let mut x = 1;
80            let expected = (1..=n).find_map(|i| {
81                x = x * a % n;
82                if x == 1 { Some(i) } else { None }
83            });
84            eprintln!("{:?}", (a, n));
85            assert_eq!(actual, expected);
86        }
87    }
88}
nekolib/math/mod_ord.rs

nekolib/math/
mod_ord.rs
