malachite_base/num/factorization/
primitive_root_prime.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// Uses code adopted from the FLINT Library.
4//
5//      Copyright © 2013 Mike Hansen
6//
7//      Copyright © 2024 Vincent Neiger
8//
9// This file is part of Malachite.
10//
11// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
12// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
13// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
14
15use crate::num::basic::unsigneds::PrimitiveUnsigned;
16use crate::num::exhaustive::primitive_int_increasing_range;
17use crate::num::factorization::factor::{
18    MAX_FACTORS_IN_U8, MAX_FACTORS_IN_U16, MAX_FACTORS_IN_U32, MAX_FACTORS_IN_U64,
19    MAX_FACTORS_IN_USIZE,
20};
21use crate::num::factorization::traits::{Factor, IsPrime, PrimitiveRootPrime};
22
23// This is n_primitive_root_prime from ulong_extras/primitive_root_prime.c, FLINT 3.3.0-dev.
24pub fn primitive_root_prime<T: PrimitiveUnsigned + IsPrime + Factor, const N: usize>(p: T) -> T
25where
26    <T as Factor>::FACTORS: Clone + IntoIterator<Item = (T, u8)>,
27{
28    assert!(p > T::ONE);
29    if p == T::TWO {
30        return T::ONE;
31    }
32    // compute (p - 1) / factors once and for all
33    let mut exponents = [T::ZERO; N];
34    let pm1 = p - T::ONE;
35    for (e, (pf, _)) in exponents.iter_mut().zip((p - T::ONE).factor().into_iter()) {
36        *e = pm1 / pf;
37    }
38    // try 2, 3, ..., p - 1
39    let data = T::precompute_mod_pow_data(&p);
40    'outer: for a in primitive_int_increasing_range(T::TWO, p) {
41        for &exponent in &exponents {
42            if exponent == T::ZERO {
43                break;
44            }
45            if a.mod_pow_precomputed(exponent.wrapping_into(), p, &data) == T::ONE {
46                continue 'outer;
47            }
48        }
49        return a;
50    }
51    // If we haven't found a primitive root, it must be because p is not prime. Confirm this by
52    // failing an assertion, which will produce an appropriate error message.
53    assert!(p.is_prime());
54    unreachable!()
55}
56
57macro_rules! impl_primitive_root_prime {
58    ($t:ident, $n:ident) => {
59        impl PrimitiveRootPrime for $t {
60            type Output = $t;
61
62            /// Given a prime number, computes a primitive root modulo that number. In other words,
63            /// given a prime $p$, finds a generator of the cyclic group
64            /// $(\mathbb{Z}/p\mathbb{Z})^\times$.
65            ///
66            /// If the input is not prime, this function's behavior is unspecified. Since primality
67            /// checking can be expensive, the input is not tested for primality.
68            ///
69            /// Currently the smallest primitive root is returned, but there is no guarantee that
70            /// this will be the case in the future.
71            ///
72            /// # Worst-case complexity
73            /// $T(n) = O(2^{n/4})$
74            ///
75            /// $M(n) = O(1)$
76            ///
77            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
78            ///
79            /// # Panics
80            /// Panics if `self` is 0, and possibly panics if `self` is not prime.
81            ///
82            /// # Examples
83            /// ```
84            /// use malachite_base::num::factorization::traits::PrimitiveRootPrime;
85            ///
86            /// assert_eq!(5u32.primitive_root_prime(), 2);
87            /// assert_eq!(191u32.primitive_root_prime(), 19);
88            /// assert_eq!(4294967291u32.primitive_root_prime(), 2);
89            /// ```
90            #[inline]
91            fn primitive_root_prime(&self) -> $t {
92                primitive_root_prime::<$t, $n>(*self)
93            }
94        }
95    };
96}
97impl_primitive_root_prime!(u8, MAX_FACTORS_IN_U8);
98impl_primitive_root_prime!(u16, MAX_FACTORS_IN_U16);
99impl_primitive_root_prime!(u32, MAX_FACTORS_IN_U32);
100impl_primitive_root_prime!(u64, MAX_FACTORS_IN_U64);
101impl_primitive_root_prime!(usize, MAX_FACTORS_IN_USIZE);
malachite_base/num/factorization/primitive_root_prime.rs

malachite_base/num/factorization/
primitive_root_prime.rs
