FactorPolyField

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 methods
    fn factor_poly_with_controller<P, Controller>(
        poly_ring: P,
        poly: &El<P>,
        _: Controller,
    ) -> (Vec<(El<P>, usize)>, Self::Element)
       where P: RingStore + Copy,
             P::Type: PolyRing + EuclideanRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
             Controller: ComputationController { ... }
    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 factor_poly_with_controller<P, Controller>( poly_ring: P, poly: &El<P>, _: Controller, ) -> (Vec<(El<P>, usize)>, Self::Element)
where P: RingStore + Copy, P::Type: PolyRing + EuclideanRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>, Controller: ComputationController,

As FactorPolyField::factor_poly(), this computes the factorization of a polynomial. However, it additionally accepts a ComputationController to customize the performed computation.

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>,

Returns whether the given polynomial is irreducible over the base field.

This is functionally equivalent to checking whether the output of FactorPolyField::factor_poly() has only a single factor, but may be faster.

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§