haar_lib/math/
primitive_root.rs

1//! 原始根
2
3use crate::for_loop;
4use crate::math::mod_ops::pow::*;
5
6/// 原始根
7pub const fn primitive_root(p: u32) -> u32 {
8    let mut pf = [0; 32];
9    let mut n = p - 1;
10    let mut j = 0;
11    let mut i = 2;
12    while i * i <= n {
13        if n % i == 0 {
14            while n % i == 0 {
15                n /= i;
16            }
17            pf[j] = i;
18            j += 1;
19        }
20        i += 1
21    }
22
23    if n != 1 {
24        pf[j] = n;
25    }
26
27    for_loop!(let mut g = 2; g <= p; g += 1; {
28        let mut ok = true;
29
30        for_loop!(let mut i = 0; i < pf.len(); i += 1; {
31            let f = pf[i];
32            if f == 0 {
33                break;
34            }
35            if mod_pow(g as u64, (p as u64 - 1) / f as u64, p as u64) == 1 {
36                ok = false;
37                break;
38            }
39        });
40
41        if ok {
42            return g;
43        }
44    });
45
46    panic!("No primitive roots.");
47}
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test() {
55        assert_eq!(primitive_root(469762049), 3);
56        assert_eq!(primitive_root(167772161), 3);
57        assert_eq!(primitive_root(754974721), 11);
58        assert_eq!(primitive_root(1012924417), 5);
59
60        struct A<const P: u32, const PR: u32>;
61        impl<const P: u32, const PR: u32> A<P, PR> {
62            fn print(&self) {
63                dbg!(P, PR);
64            }
65        }
66
67        let a = A::<998244353, { primitive_root(998244353) }>;
68        a.print();
69    }
70}
haar_lib/math/primitive_root.rs

haar_lib/math/
primitive_root.rs
