feanor_math::algorithms::poly_factor

Trait FactorPolyField

Source 
pub trait FactorPolyField: Field + PolyTFracGCDRing {
    // Required method
    fn factor_poly<P>(
        poly_ring: P,
        poly: &El<P>,
    ) -> (Vec<(El<P>, usize)>, Self::Element)
       where P: RingStore + Copy,
             P::Type: PolyRing + EuclideanRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>;

    // Provided method
    fn is_irred<P>(poly_ring: P, poly: &El<P>) -> bool
       where P: RingStore + Copy,
             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§

Source

fn factor_poly<P>( poly_ring: P, poly: &El<P>, ) -> (Vec<(El<P>, usize)>, Self::Element)
where P: RingStore + Copy, P::Type: PolyRing + EuclideanRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,

Factors a univariate polynomial with coefficients in this field into its irreducible factors.

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);

Provided Methods§

Source

fn is_irred<P>(poly_ring: P, poly: &El<P>) -> bool
where P: RingStore + Copy, P::Type: PolyRing + EuclideanRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§