haar_lib/math/
primitive_root.rs

1//! 原始根
2
3use crate::math::{factorize::trial::*, mod_ops::pow::*};
4
5/// 原始根
6pub fn primitive_root(p: u64) -> Option<u64> {
7    let pf = factorize(p - 1)
8        .into_iter()
9        .map(|(x, _)| x)
10        .collect::<Vec<_>>();
11
12    (2..=p).find(|&g| pf.iter().all(|f| mod_pow(g, (p - 1) / f, p) != 1))
13}
14
15#[cfg(test)]
16mod tests {
17    use super::*;
18
19    #[test]
20    fn test() {
21        assert_eq!(primitive_root(469762049), Some(3));
22        assert_eq!(primitive_root(167772161), Some(3));
23        assert_eq!(primitive_root(754974721), Some(11));
24        assert_eq!(primitive_root(1012924417), Some(5));
25    }
26}