Trait feanor_math::algorithms::poly_factor::FactorPolyField
source · pub trait FactorPolyField: Field {
// Required method
fn factor_poly<P>(
poly_ring: P,
poly: &El<P>,
) -> (Vec<(El<P>, usize)>, Self::Element)
where P: PolyRingStore,
P::Type: PolyRing + EuclideanRing,
<P::Type as RingExtension>::BaseRing: RingStore<Type = Self>;
}Expand description
Trait for fields over which we can efficiently factor polynomials.
For details, see the only associated function FactorPolyField::factor_poly().
Required Methods§
sourcefn factor_poly<P>(
poly_ring: P,
poly: &El<P>,
) -> (Vec<(El<P>, usize)>, Self::Element)where
P: PolyRingStore,
P::Type: PolyRing + EuclideanRing,
<P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
fn factor_poly<P>(
poly_ring: P,
poly: &El<P>,
) -> (Vec<(El<P>, usize)>, Self::Element)where
P: PolyRingStore,
P::Type: PolyRing + EuclideanRing,
<P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
Factors a univariate polynomial with coefficients in this ring into its irreducible factors.
This requires that this ring is a UFD, otherwise a unique factorization does not exist in
the corresponding polynomial ring.
All factors must be monic and but may be returned in any order (with multiplicities). The
unit poly / prod_i factor[i]^multiplicity[i] (which is a unit in the base ring) is returned
as second tuple element.
§Example - factorization over QQ
// Unfortunately, the internal gcd computations will *extremely* blow up coefficients;
// If you are unsure, use BigIntRing::RING as underlying implementation of ZZ
let ZZ = StaticRing::<i128>::RING;
let QQ = RationalField::new(ZZ);
let P = dense_poly::DensePolyRing::new(QQ, "X");
let ZZ_to_QQ = QQ.can_hom(&ZZ).unwrap();
let fraction = |nom: i128, den: i128| QQ.div(&ZZ_to_QQ.map(nom), &ZZ_to_QQ.map(den));
// f is X^2 + 3/2
let f = P.from_terms([(fraction(3, 2), 0), (fraction(1, 1), 2)].into_iter());
// g is X^2 + 2/3 X + 1
let g = P.from_terms([(fraction(1, 1), 0), (fraction(2, 3), 1), (fraction(1, 1), 2)].into_iter());
let fgg = P.prod([&f, &g, &g, &P.int_hom().map(6)].iter().map(|poly| P.clone_el(poly)));
let (factorization, unit) = <RationalFieldBase<_> as FactorPolyField>::factor_poly(&P, &fgg);
assert_eq!(2, factorization.len());
if P.eq_el(&f, &factorization[0].0) {
assert_eq!(1, factorization[0].1);
assert_eq!(2, factorization[1].1);
assert_el_eq!(&P, &g, &factorization[1].0);
} else {
assert_eq!(2, factorization[0].1);
assert_eq!(1, factorization[1].1);
assert_el_eq!(&P, &g, &factorization[0].0);
assert_el_eq!(&P, &f, &factorization[1].0);
}
assert_el_eq!(&QQ, &ZZ_to_QQ.map(6), &unit);Object Safety§
This trait is not object safe.