feanor_math/algorithms/poly_factor/
mod.rs

1use finite::*;
2use rational::*;
3
4use super::poly_gcd::PolyTFracGCDRing;
5use crate::computation::*;
6use crate::field::*;
7use crate::homomorphism::*;
8use crate::integer::*;
9use crate::pid::*;
10use crate::ring::*;
11use crate::rings::finite::FiniteRing;
12use crate::rings::poly::*;
13use crate::rings::rational::*;
14use crate::rings::zn::zn_64::*;
15
16/// Contains an implementation of the Cantor-Zassenhaus algorithm for
17/// finding factors of univariate polynomials over finite fields.
18///
19/// Additionally, a distinct-degree factorization and variants of Cantor-
20/// Zassenhaus are also implemented.
21pub mod cantor_zassenhaus;
22/// Contains algorithms for computing the factorization of polynomials.
23///
24/// TODO: move to [`crate::algorithms::poly_factor`].
25pub mod factor_locally;
26
27/// Contains an an algorithm to factor univariate polynomials over
28/// field extensions.
29pub mod extension;
30
31/// Contains an algorithm to factor univariate polynomials over the integers
32/// and the rational numbers.
33pub mod rational;
34
35/// Contains an algorithm to factor univariate polynomials over finite fields,
36/// based on the more basic functionality of [`cantor_zassenhaus`].
37pub mod finite;
38
39/// Trait for fields over which we can efficiently factor polynomials.
40/// For details, see the only associated function [`FactorPolyField::factor_poly()`].
41pub trait FactorPolyField: Field + PolyTFracGCDRing {
42    /// Factors a univariate polynomial with coefficients in this field into its irreducible
43    /// factors.
44    ///
45    /// All factors must be monic and but may be returned in any order (with multiplicities). The
46    /// unit `poly / prod_i factor[i]^multiplicity[i]` (which is a unit in the base ring) is
47    /// returned as second tuple element.
48    ///
49    /// # Example - factorization over `QQ`
50    /// ```rust
51    /// # use feanor_math::ring::*;
52    /// # use feanor_math::primitive_int::*;
53    /// # use feanor_math::rings::poly::*;
54    /// # use feanor_math::rings::rational::*;
55    /// # use feanor_math::homomorphism::*;
56    /// # use feanor_math::assert_el_eq;
57    /// # use feanor_math::field::*;
58    /// # use feanor_math::algorithms::poly_factor::*;
59    /// // Unfortunately, the internal gcd computations will *extremely* blow up coefficients;
60    /// // If you are unsure, use BigIntRing::RING as underlying implementation of ZZ
61    /// let ZZ = StaticRing::<i128>::RING;
62    /// let QQ = RationalField::new(ZZ);
63    /// let P = dense_poly::DensePolyRing::new(QQ, "X");
64    /// let ZZ_to_QQ = QQ.can_hom(&ZZ).unwrap();
65    /// let fraction = |nom: i128, den: i128| QQ.div(&ZZ_to_QQ.map(nom), &ZZ_to_QQ.map(den));
66    ///
67    /// // f is X^2 + 3/2
68    /// let f = P.from_terms([(fraction(3, 2), 0), (fraction(1, 1), 2)].into_iter());
69    ///
70    /// // g is X^2 + 2/3 X + 1
71    /// let g = P.from_terms(
72    ///     [
73    ///         (fraction(1, 1), 0),
74    ///         (fraction(2, 3), 1),
75    ///         (fraction(1, 1), 2),
76    ///     ]
77    ///     .into_iter(),
78    /// );
79    ///
80    /// let fgg = P.prod(
81    ///     [&f, &g, &g, &P.int_hom().map(6)]
82    ///         .iter()
83    ///         .map(|poly| P.clone_el(poly)),
84    /// );
85    /// let (factorization, unit) = <RationalFieldBase<_> as FactorPolyField>::factor_poly(&P, &fgg);
86    /// assert_eq!(2, factorization.len());
87    /// if P.eq_el(&f, &factorization[0].0) {
88    ///     assert_eq!(1, factorization[0].1);
89    ///     assert_eq!(2, factorization[1].1);
90    ///     assert_el_eq!(P, g, factorization[1].0);
91    /// } else {
92    ///     assert_eq!(2, factorization[0].1);
93    ///     assert_eq!(1, factorization[1].1);
94    ///     assert_el_eq!(P, g, factorization[0].0);
95    ///     assert_el_eq!(P, f, factorization[1].0);
96    /// }
97    /// assert_el_eq!(QQ, ZZ_to_QQ.map(6), unit);
98    /// ```
99    fn factor_poly<P>(poly_ring: P, poly: &El<P>) -> (Vec<(El<P>, usize)>, Self::Element)
100    where
101        P: RingStore + Copy,
102        P::Type: PolyRing + EuclideanRing,
103        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>;
104
105    /// As [`FactorPolyField::factor_poly()`], this computes the factorization of
106    /// a polynomial. However, it additionally accepts a [`ComputationController`]
107    /// to customize the performed computation.
108    fn factor_poly_with_controller<P, Controller>(
109        poly_ring: P,
110        poly: &El<P>,
111        _: Controller,
112    ) -> (Vec<(El<P>, usize)>, Self::Element)
113    where
114        P: RingStore + Copy,
115        P::Type: PolyRing + EuclideanRing,
116        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
117        Controller: ComputationController,
118    {
119        Self::factor_poly(poly_ring, poly)
120    }
121
122    /// Returns whether the given polynomial is irreducible over the base field.
123    ///
124    /// This is functionally equivalent to checking whether the output of
125    /// [`FactorPolyField::factor_poly()`] has only a single factor, but may be faster.
126    fn is_irred<P>(poly_ring: P, poly: &El<P>) -> bool
127    where
128        P: RingStore + Copy,
129        P::Type: PolyRing + EuclideanRing,
130        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
131    {
132        let factorization = Self::factor_poly(poly_ring, poly).0;
133        return factorization.len() == 1 && factorization[0].1 == 1;
134    }
135}
136
137impl<R: ?Sized> FactorPolyField for R
138where
139    R: FiniteRing + Field + SelfIso,
140{
141    fn factor_poly<P>(poly_ring: P, poly: &El<P>) -> (Vec<(El<P>, usize)>, Self::Element)
142    where
143        P: RingStore + Copy,
144        P::Type: PolyRing + EuclideanRing,
145        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
146    {
147        Self::factor_poly_with_controller(poly_ring, poly, DontObserve)
148    }
149
150    fn factor_poly_with_controller<P, Controller>(
151        poly_ring: P,
152        poly: &El<P>,
153        controller: Controller,
154    ) -> (Vec<(El<P>, usize)>, Self::Element)
155    where
156        P: RingStore,
157        P::Type: PolyRing + EuclideanRing,
158        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
159        Controller: ComputationController,
160    {
161        poly_factor_finite_field(poly_ring, poly, controller)
162    }
163}
164
165impl<I> FactorPolyField for RationalFieldBase<I>
166where
167    I: RingStore,
168    I::Type: IntegerRing,
169    ZnBase: CanHomFrom<I::Type>,
170{
171    fn factor_poly<P>(poly_ring: P, poly: &El<P>) -> (Vec<(El<P>, usize)>, Self::Element)
172    where
173        P: RingStore + Copy,
174        P::Type: PolyRing + EuclideanRing,
175        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
176    {
177        Self::factor_poly_with_controller(poly_ring, poly, DontObserve)
178    }
179
180    fn factor_poly_with_controller<P, Controller>(
181        poly_ring: P,
182        poly: &El<P>,
183        controller: Controller,
184    ) -> (Vec<(El<P>, usize)>, Self::Element)
185    where
186        P: RingStore + Copy,
187        P::Type: PolyRing + EuclideanRing,
188        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
189        Controller: ComputationController,
190    {
191        poly_factor_rational(poly_ring, poly, controller)
192    }
193}
194
195#[cfg(test)]
196use crate::rings::poly::dense_poly::DensePolyRing;
197#[cfg(test)]
198use crate::rings::zn::*;
199
200#[test]
201fn test_factor_rational_poly() {
202    let QQ = RationalField::new(BigIntRing::RING);
203    let incl = QQ.int_hom();
204    let poly_ring = DensePolyRing::new(&QQ, "X");
205    let f = poly_ring.from_terms([(incl.map(2), 0), (incl.map(1), 3)].into_iter());
206    let g = poly_ring.from_terms([(incl.map(1), 0), (incl.map(2), 1), (incl.map(1), 2), (incl.map(1), 4)].into_iter());
207    let (actual, unit) = <_ as FactorPolyField>::factor_poly(
208        &poly_ring,
209        &poly_ring.prod([poly_ring.clone_el(&f), poly_ring.clone_el(&f), poly_ring.clone_el(&g)].into_iter()),
210    );
211    assert_eq!(2, actual.len());
212    assert_el_eq!(poly_ring, f, actual[0].0);
213    assert_eq!(2, actual[0].1);
214    assert_el_eq!(poly_ring, g, actual[1].0);
215    assert_eq!(1, actual[1].1);
216    assert_el_eq!(QQ, QQ.one(), unit);
217
218    let f = poly_ring.from_terms([(incl.map(3), 0), (incl.map(1), 1)]);
219    let (actual, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &f);
220    assert_eq!(1, actual.len());
221    assert_eq!(1, actual[0].1);
222    assert_el_eq!(&poly_ring, f, &actual[0].0);
223    assert_el_eq!(QQ, QQ.one(), unit);
224
225    let [mut f] = poly_ring.with_wrapped_indeterminate(|X| {
226        [16 - 32 * X + 104 * X.pow_ref(2) - 8 * 11 * X.pow_ref(3) + 121 * X.pow_ref(4)]
227    });
228    poly_ring
229        .inclusion()
230        .mul_assign_map(&mut f, QQ.div(&QQ.one(), &QQ.int_hom().map(121)));
231    let (actual, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &f);
232    assert_eq!(1, actual.len());
233    assert_eq!(2, actual[0].1);
234    assert_el_eq!(QQ, QQ.one(), unit);
235}
236
237#[test]
238fn test_factor_nonmonic_poly() {
239    let QQ = RationalField::new(BigIntRing::RING);
240    let incl = QQ.int_hom();
241    let poly_ring = DensePolyRing::new(&QQ, "X");
242    let f = poly_ring.from_terms([(QQ.div(&incl.map(3), &incl.map(5)), 0), (incl.map(1), 4)].into_iter());
243    let g = poly_ring.from_terms([(incl.map(1), 0), (incl.map(2), 1), (incl.map(1), 2), (incl.map(1), 4)].into_iter());
244    let (actual, unit) = <_ as FactorPolyField>::factor_poly(
245        &poly_ring,
246        &poly_ring.prod(
247            [
248                poly_ring.clone_el(&f),
249                poly_ring.clone_el(&f),
250                poly_ring.clone_el(&g),
251                poly_ring.int_hom().map(100),
252            ]
253            .into_iter(),
254        ),
255    );
256    assert_eq!(2, actual.len());
257
258    assert_el_eq!(poly_ring, g, actual[0].0);
259    assert_eq!(1, actual[0].1);
260    assert_el_eq!(poly_ring, f, actual[1].0);
261    assert_eq!(2, actual[1].1);
262    assert_el_eq!(QQ, incl.map(100), unit);
263}
264
265#[test]
266fn test_factor_fp() {
267    let Fp = zn_static::Fp::<5>::RING;
268    let poly_ring = DensePolyRing::new(Fp, "X");
269    let f = poly_ring.from_terms([(1, 0), (2, 1), (1, 3)].into_iter());
270    let g = poly_ring.from_terms([(1, 0), (1, 1)].into_iter());
271    let h = poly_ring.from_terms([(2, 0), (1, 2)].into_iter());
272    let fgghhh = poly_ring.prod([&f, &g, &g, &h, &h, &h].iter().map(|poly| poly_ring.clone_el(poly)));
273    let (factorization, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &fgghhh);
274    assert_el_eq!(Fp, Fp.one(), unit);
275
276    assert_eq!(2, factorization[0].1);
277    assert_el_eq!(poly_ring, g, factorization[0].0);
278    assert_eq!(3, factorization[1].1);
279    assert_el_eq!(poly_ring, h, factorization[1].0);
280    assert_eq!(1, factorization[2].1);
281    assert_el_eq!(poly_ring, f, factorization[2].0);
282}
feanor_math/algorithms/poly_factor/mod.rs

feanor_math/algorithms/poly_factor/
mod.rs
