feanor_math/algorithms/poly_factor/
rational.rs

1use super::IntegerRing;
2use crate::algorithms::eea::signed_lcm;
3use crate::algorithms::poly_factor::factor_locally::poly_factor_integer;
4use crate::computation::*;
5use crate::divisibility::*;
6use crate::homomorphism::*;
7use crate::pid::EuclideanRing;
8use crate::ring::*;
9use crate::rings::poly::dense_poly::DensePolyRing;
10use crate::rings::poly::*;
11use crate::rings::rational::RationalFieldBase;
12use crate::rings::zn::zn_64::*;
13
14#[stability::unstable(feature = "enable")]
15pub fn poly_factor_rational<'a, P, I, Controller>(
16    poly_ring: P,
17    poly: &El<P>,
18    controller: Controller,
19) -> (Vec<(El<P>, usize)>, El<<P::Type as RingExtension>::BaseRing>)
20where
21    P: RingStore,
22    P::Type: PolyRing + EuclideanRing,
23    <P::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
24    I: RingStore,
25    I::Type: IntegerRing,
26    ZnBase: CanHomFrom<I::Type>,
27    Controller: ComputationController,
28{
29    assert!(!poly_ring.is_zero(poly));
30    let QQX = &poly_ring;
31    let QQ = QQX.base_ring();
32    let ZZ = QQ.base_ring();
33
34    let den_lcm = QQX
35        .terms(poly)
36        .map(|(c, _)| QQ.get_ring().den(c))
37        .fold(ZZ.one(), |a, b| signed_lcm(a, ZZ.clone_el(b), ZZ));
38
39    let ZZX = DensePolyRing::new(ZZ, "X");
40    let f = ZZX.from_terms(QQX.terms(poly).map(|(c, i)| {
41        (
42            ZZ.checked_div(&ZZ.mul_ref(&den_lcm, QQ.get_ring().num(c)), QQ.get_ring().den(c))
43                .unwrap(),
44            i,
45        )
46    }));
47    let mut factorization = poly_factor_integer(&ZZX, f, controller);
48    factorization.sort_unstable_by_key(|(factor, e)| (ZZX.degree(factor).unwrap(), *e));
49
50    let ZZX_to_QQX = QQX.lifted_hom(&ZZX, QQ.inclusion());
51    return (
52        factorization
53            .into_iter()
54            .map(|(f, e)| (QQX.normalize(ZZX_to_QQX.map(f)), e))
55            .collect(),
56        QQ.clone_el(QQX.lc(poly).unwrap()),
57    );
58}
feanor_math/algorithms/poly_factor/rational.rs

feanor_math/algorithms/poly_factor/
rational.rs
