feanor_math/algorithms/poly_factor/
mod.rs

1use crate::field::*;
2use crate::homomorphism::*;
3use crate::integer::*;
4use crate::pid::*;
5use crate::ring::*;
6use crate::rings::finite::FiniteRing;
7use crate::rings::poly::*;
8use crate::rings::rational::*;
9use crate::rings::zn::zn_64::*;
10
11use finite::*;
12use rational::*;
13
14pub mod cantor_zassenhaus;
15pub mod extension;
16pub mod rational;
17pub mod finite;
18
19///
20/// Trait for fields over which we can efficiently factor polynomials.
21/// For details, see the only associated function [`FactorPolyField::factor_poly()`].
22/// 
23pub trait FactorPolyField: Field + PolyTFracGCDRing {
24
25    ///
26    /// Factors a univariate polynomial with coefficients in this field into its irreducible factors.
27    /// 
28    /// All factors must be monic and but may be returned in any order (with multiplicities). The
29    /// unit `poly / prod_i factor[i]^multiplicity[i]` (which is a unit in the base ring) is returned
30    /// as second tuple element.
31    /// 
32    /// # Example - factorization over `QQ`
33    /// ```
34    /// # use feanor_math::ring::*;
35    /// # use feanor_math::primitive_int::*;
36    /// # use feanor_math::rings::poly::*;
37    /// # use feanor_math::rings::rational::*;
38    /// # use feanor_math::homomorphism::*;
39    /// # use feanor_math::assert_el_eq;
40    /// # use feanor_math::field::*;
41    /// # use feanor_math::algorithms::poly_factor::*;
42    /// // Unfortunately, the internal gcd computations will *extremely* blow up coefficients;
43    /// // If you are unsure, use BigIntRing::RING as underlying implementation of ZZ
44    /// let ZZ = StaticRing::<i128>::RING;
45    /// let QQ = RationalField::new(ZZ);
46    /// let P = dense_poly::DensePolyRing::new(QQ, "X");
47    /// let ZZ_to_QQ = QQ.can_hom(&ZZ).unwrap();
48    /// let fraction = |nom: i128, den: i128| QQ.div(&ZZ_to_QQ.map(nom), &ZZ_to_QQ.map(den));
49    /// 
50    /// // f is X^2 + 3/2
51    /// let f = P.from_terms([(fraction(3, 2), 0), (fraction(1, 1), 2)].into_iter());
52    /// 
53    /// // g is X^2 + 2/3 X + 1
54    /// let g = P.from_terms([(fraction(1, 1), 0), (fraction(2, 3), 1), (fraction(1, 1), 2)].into_iter());
55    /// 
56    /// let fgg = P.prod([&f, &g, &g, &P.int_hom().map(6)].iter().map(|poly| P.clone_el(poly)));
57    /// let (factorization, unit) = <RationalFieldBase<_> as FactorPolyField>::factor_poly(&P, &fgg);
58    /// assert_eq!(2, factorization.len());
59    /// if P.eq_el(&f, &factorization[0].0) {
60    ///     assert_eq!(1, factorization[0].1);
61    ///     assert_eq!(2, factorization[1].1);
62    ///     assert_el_eq!(P, g, factorization[1].0);
63    /// } else {
64    ///     assert_eq!(2, factorization[0].1);
65    ///     assert_eq!(1, factorization[1].1);
66    ///     assert_el_eq!(P, g, factorization[0].0);
67    ///     assert_el_eq!(P, f, factorization[1].0);
68    /// }
69    /// assert_el_eq!(QQ, ZZ_to_QQ.map(6), unit);
70    /// ```
71    /// 
72    fn factor_poly<P>(poly_ring: P, poly: &El<P>) -> (Vec<(El<P>, usize)>, Self::Element)
73        where P: RingStore + Copy,
74            P::Type: PolyRing + EuclideanRing,
75            <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>;
76
77    fn is_irred<P>(poly_ring: P, poly: &El<P>) -> bool
78        where P: RingStore + Copy,
79            P::Type: PolyRing + EuclideanRing,
80            <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>
81    {
82        let factorization = Self::factor_poly(poly_ring, poly).0;
83        return factorization.len() == 1 && factorization[0].1 == 1;
84    }
85}
86
87impl<R> FactorPolyField for R
88    where R: FiniteRing + Field + SelfIso
89{
90    fn factor_poly<P>(poly_ring: P, poly: &El<P>) -> (Vec<(El<P>, usize)>, Self::Element)
91        where P: RingStore,
92            P::Type: PolyRing + EuclideanRing,
93            <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>
94    {
95        poly_factor_finite_field(poly_ring, poly)
96    }
97}
98
99impl<I> FactorPolyField for RationalFieldBase<I>
100    where I: RingStore,
101        I::Type: IntegerRing,
102        ZnBase: CanHomFrom<I::Type>
103{
104    fn factor_poly<P>(poly_ring: P, poly: &El<P>) -> (Vec<(El<P>, usize)>, Self::Element)
105        where P: RingStore,
106            P::Type: PolyRing + EuclideanRing,
107            <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>
108    {
109        poly_factor_rational(poly_ring, poly)
110    }
111}
112
113#[cfg(test)]
114use crate::rings::poly::dense_poly::DensePolyRing;
115#[cfg(test)]
116use crate::rings::zn::*;
117
118use super::poly_gcd::PolyTFracGCDRing;
119
120#[test]
121fn test_factor_rational_poly() {
122    let QQ = RationalField::new(BigIntRing::RING);
123    let incl = QQ.int_hom();
124    let poly_ring = DensePolyRing::new(&QQ, "X");
125    let f = poly_ring.from_terms([(incl.map(2), 0), (incl.map(1), 3)].into_iter());
126    let g = poly_ring.from_terms([(incl.map(1), 0), (incl.map(2), 1), (incl.map(1), 2), (incl.map(1), 4)].into_iter());
127    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()));
128    assert_eq!(2, actual.len());
129    assert_el_eq!(poly_ring, f, actual[0].0);
130    assert_eq!(2, actual[0].1);
131    assert_el_eq!(poly_ring, g, actual[1].0);
132    assert_eq!(1, actual[1].1);
133    assert_el_eq!(QQ, QQ.one(), unit);
134
135    let f = poly_ring.from_terms([(incl.map(3), 0), (incl.map(1), 1)]);
136    let (actual, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &f);
137    assert_eq!(1, actual.len());
138    assert_eq!(1, actual[0].1);
139    assert_el_eq!(&poly_ring, f, &actual[0].0);
140    assert_el_eq!(QQ, QQ.one(), unit);
141
142    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)]);
143    poly_ring.inclusion().mul_assign_map(&mut f, QQ.div(&QQ.one(), &QQ.int_hom().map(121)));
144    let (actual, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &f);
145    assert_eq!(1, actual.len());
146    assert_eq!(2, actual[0].1);
147    assert_el_eq!(QQ, QQ.one(), unit);
148}
149
150#[test]
151fn test_factor_nonmonic_poly() {
152    let QQ = RationalField::new(BigIntRing::RING);
153    let incl = QQ.int_hom();
154    let poly_ring = DensePolyRing::new(&QQ, "X");
155    let f = poly_ring.from_terms([(QQ.div(&incl.map(3), &incl.map(5)), 0), (incl.map(1), 4)].into_iter());
156    let g = poly_ring.from_terms([(incl.map(1), 0), (incl.map(2), 1), (incl.map(1), 2), (incl.map(1), 4)].into_iter());
157    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()));
158    assert_eq!(2, actual.len());
159
160    assert_el_eq!(poly_ring, g, actual[0].0);
161    assert_eq!(1, actual[0].1);
162    assert_el_eq!(poly_ring, f, actual[1].0);
163    assert_eq!(2, actual[1].1);
164    assert_el_eq!(QQ, incl.map(100), unit);
165}
166
167#[test]
168fn test_factor_fp() {
169    let Fp = zn_static::Fp::<5>::RING;
170    let poly_ring = DensePolyRing::new(Fp, "X");
171    let f = poly_ring.from_terms([(1, 0), (2, 1), (1, 3)].into_iter());
172    let g = poly_ring.from_terms([(1, 0), (1, 1)].into_iter());
173    let h = poly_ring.from_terms([(2, 0), (1, 2)].into_iter());
174    let fgghhh = poly_ring.prod([&f, &g, &g, &h, &h, &h].iter().map(|poly| poly_ring.clone_el(poly)));
175    let (factorization, unit) = <_ as FactorPolyField>::factor_poly(&poly_ring, &fgghhh);
176    assert_el_eq!(Fp, Fp.one(), unit);
177    
178    assert_eq!(2, factorization[0].1);
179    assert_el_eq!(poly_ring, g, factorization[0].0);
180    assert_eq!(3, factorization[1].1);
181    assert_el_eq!(poly_ring, h, factorization[1].0);
182    assert_eq!(1, factorization[2].1);
183    assert_el_eq!(poly_ring, f, factorization[2].0);
184}
feanor_math/algorithms/poly_factor/mod.rs

feanor_math/algorithms/poly_factor/
mod.rs
