feanor-math 3.5.18

A library for number theory, providing implementations for arithmetic in various rings and algorithms working on them.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

use super::IntegerRing;
use crate::algorithms::eea::signed_lcm;
use crate::algorithms::poly_factor::factor_locally::poly_factor_integer;
use crate::computation::*;
use crate::divisibility::*;
use crate::homomorphism::*;
use crate::pid::EuclideanRing;
use crate::ring::*;
use crate::rings::poly::dense_poly::DensePolyRing;
use crate::rings::poly::*;
use crate::rings::rational::RationalFieldBase;
use crate::rings::zn::zn_64::*;

#[stability::unstable(feature = "enable")]
pub fn poly_factor_rational<'a, P, I, Controller>(
    poly_ring: P,
    poly: &El<P>,
    controller: Controller,
) -> (Vec<(El<P>, usize)>, El<<P::Type as RingExtension>::BaseRing>)
where
    P: RingStore,
    P::Type: PolyRing + EuclideanRing,
    <P::Type as RingExtension>::BaseRing: RingStore<Type = RationalFieldBase<I>>,
    I: RingStore,
    I::Type: IntegerRing,
    ZnBase: CanHomFrom<I::Type>,
    Controller: ComputationController,
{
    assert!(!poly_ring.is_zero(poly));
    let QQX = &poly_ring;
    let QQ = QQX.base_ring();
    let ZZ = QQ.base_ring();

    let den_lcm = QQX
        .terms(poly)
        .map(|(c, _)| QQ.get_ring().den(c))
        .fold(ZZ.one(), |a, b| signed_lcm(a, ZZ.clone_el(b), ZZ));

    let ZZX = DensePolyRing::new(ZZ, "X");
    let f = ZZX.from_terms(QQX.terms(poly).map(|(c, i)| {
        (
            ZZ.checked_div(&ZZ.mul_ref(&den_lcm, QQ.get_ring().num(c)), QQ.get_ring().den(c))
                .unwrap(),
            i,
        )
    }));
    let mut factorization = poly_factor_integer(&ZZX, f, controller);
    factorization.sort_unstable_by_key(|(factor, e)| (ZZX.degree(factor).unwrap(), *e));

    let ZZX_to_QQX = QQX.lifted_hom(&ZZX, QQ.inclusion());
    return (
        factorization
            .into_iter()
            .map(|(f, e)| (QQX.normalize(ZZX_to_QQX.map(f)), e))
            .collect(),
        QQ.clone_el(QQX.lc(poly).unwrap()),
    );
}