feanor_math/algorithms/poly_factor/
finite.rs

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

feanor_math/algorithms/poly_factor/
finite.rs
