feanor_math/algorithms/poly_factor/
mod.rs

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

feanor_math/algorithms/poly_factor/
mod.rs
