feanor_math/algorithms/poly_factor/
finite.rs

1use crate::algorithms::poly_gcd::finite::poly_squarefree_part_finite_field;
2use crate::computation::ComputationController;
3use crate::divisibility::*;
4use crate::field::*;
5use crate::integer::*;
6use crate::pid::*;
7use crate::ring::*;
8use crate::rings::finite::*;
9use crate::rings::poly::*;
10use crate::homomorphism::SelfIso;
11use super::cantor_zassenhaus;
12
13///
14/// Factors a polynomial with coefficients in a finite field.
15/// 
16#[stability::unstable(feature = "enable")]
17pub fn poly_factor_finite_field<P, Controller>(poly_ring: P, f: &El<P>, controller: Controller) -> (Vec<(El<P>, usize)>, El<<P::Type as RingExtension>::BaseRing>)
18    where P: RingStore,
19        P::Type: PolyRing + EuclideanRing,
20        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: FiniteRing + Field + SelfIso,
21        Controller: ComputationController
22{
23    assert!(!poly_ring.is_zero(&f));
24    let even_char = BigIntRing::RING.is_even(&poly_ring.base_ring().characteristic(&BigIntRing::RING).unwrap());
25
26    controller.run_computation(format_args!("factor_poly_GF(deg={})", poly_ring.degree(f).unwrap()), |controller| {
27
28        let mut result = Vec::new();
29        let mut unit = poly_ring.base_ring().one();
30        let mut el = poly_ring.clone_el(&f);
31
32        // we repeatedly remove the square-free part
33        while !poly_ring.is_unit(&el) {
34
35            let sqrfree_part = poly_squarefree_part_finite_field(&poly_ring, &el, controller.clone());
36            assert!(!poly_ring.is_unit(&sqrfree_part));
37
38            // factor the square-free part into distinct-degree factors
39            let distinct_degree_factors = cantor_zassenhaus::distinct_degree_factorization(&poly_ring, poly_ring.clone_el(&sqrfree_part), controller.clone());
40            for (d, factor_d) in distinct_degree_factors.into_iter().enumerate() {
41                let mut stack = Vec::new();
42                stack.push(factor_d);
43                
44                // and finally extract each individual factor
45                while let Some(mut current) = stack.pop() {
46                    current = poly_ring.normalize(current);
47
48                    if poly_ring.is_one(&current) {
49                        continue;
50                    } else if poly_ring.degree(&current) == Some(d) {
51                        // add to result
52                        let mut found = false;
53                        for (factor, power) in &mut result {
54                            if poly_ring.eq_el(factor, &current) {
55                                *power += 1;
56                                found = true;
57                                break;
58                            }
59                        }
60                        if !found {
61                            result.push((current, 1));
62                        }
63                    } else if even_char {
64                        let factor = cantor_zassenhaus::cantor_zassenhaus_even(&poly_ring, poly_ring.clone_el(&current), d, controller.clone());
65                        stack.push(poly_ring.checked_div(&current, &factor).unwrap());
66                        stack.push(factor);
67                    } else {
68                        let factor = cantor_zassenhaus::cantor_zassenhaus(&poly_ring, poly_ring.clone_el(&current), d, controller.clone());
69                        stack.push(poly_ring.checked_div(&current, &factor).unwrap());
70                        stack.push(factor);
71                    }
72                }
73            }
74            el = poly_ring.checked_div(&el, &sqrfree_part).unwrap();
75        }
76        poly_ring.base_ring().mul_assign_ref(&mut unit, poly_ring.coefficient_at(&el, 0));
77        debug_assert!(poly_ring.base_ring().is_unit(&unit));
78
79        return (result, unit);
80    })
81}
feanor_math/algorithms/poly_factor/finite.rs

feanor_math/algorithms/poly_factor/
finite.rs
