Skip to main content

primitive_root

competitive::math

Function primitive_root 

Source 
pub fn primitive_root(p: u64) -> u64
Examples found in repository?
crates/library_checker/src/number_theory/primitive_root.rs (line 9)
5pub fn primitive_root(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(q, p: [u64; iter q]);
8    for p in p {
9        pp!(primitive_root_library(p));
10    }
11}
More examples
Hide additional examples
crates/competitive/src/math/discrete_logarithm.rs (line 262)
260    fn new(p: u64, br_primes: &[BarrettReduction<u64>]) -> Self {
261        let ord = p - 1;
262        let g = primitive_root(p);
263        let br = BarrettReduction::<u128>::new(p as u128);
264        let prec = QdrtPowPrec::new(g, ord, &br);
265        let coeff = index_calculus_for_primitive_root(p, ord, br_primes, &prec);
266        Self {
267            p,
268            ord,
269            prec,
270            coeff,
271        }
272    }
crates/competitive/src/math/fast_prime_mod.rs (line 60)
45    pub fn new() -> Self {
46        assert!(
47            BUILD_INV || BUILD_POW,
48            "at least one of BUILD_INV or BUILD_POW must be true"
49        );
50        assert!(P < 1 << 30, "P must be less than 2^30");
51        assert!(
52            P % 2 == 1 && miller_rabin(P as u64),
53            "P must be an odd prime"
54        );
55
56        let (root, pow_lo, pow_hi, log) = if BUILD_POW {
57            let root = if P == 998_244_353 {
58                3
59            } else {
60                primitive_root(P as u64) as u32
61            };
62            let (pow_lo, pow_hi) = build_pow::<P>(root);
63            let log = build_log::<P>(root, &pow_lo, &pow_hi);
64            (root, pow_lo, pow_hi, log)
65        } else {
66            (
67                0,
68                Vec::new().into_boxed_slice(),
69                Vec::new().into_boxed_slice(),
70                Vec::new().into_boxed_slice(),
71            )
72        };
73        let inv = if BUILD_INV {
74            build_inv::<P>()
75        } else {
76            Vec::new().into_boxed_slice()
77        };
78        let frac = if is_direct_table_mod::<P>() {
79            Vec::new().into_boxed_slice()
80        } else {
81            build_frac::<P>()
82        };
83        Self {
84            root,
85            pow_lo,
86            pow_hi,
87            frac,
88            log,
89            inv,
90        }
91    }