Skip to main content

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".

Implementors§