algebraeon_rings/integer/
polynomial.rs

1use crate::{integer::*, polynomial::*};
2use std::rc::Rc;
3
4impl<B: BorrowedStructure<IntegerCanonicalStructure>> GreatestCommonDivisorSignature
5    for PolynomialStructure<IntegerCanonicalStructure, B>
6{
7    fn gcd(&self, x: &Self::Set, y: &Self::Set) -> Self::Set {
8        self.gcd_by_primitive_subresultant(x.clone(), y.clone())
9    }
10}
11
12impl<B: BorrowedStructure<IntegerCanonicalStructure>> FactoringMonoidSignature
13    for PolynomialStructure<IntegerCanonicalStructure, B>
14{
15    fn factor_unchecked(&self, p: &Self::Set) -> Factored<Polynomial<Integer>, Natural> {
16        use berlekamp_zassenhaus::factorize_by_berlekamp_zassenhaus_algorithm;
17        // self.factorize_by_kroneckers_method(p)
18        factorize_by_berlekamp_zassenhaus_algorithm(p.clone())
19    }
20}
21
22impl Polynomial<Integer> {
23    //https://en.wikipedia.org/wiki/Landau-Mignotte_bound
24    /// Return the Mignotte bound for the coefficients of any factor of $f(x)$: If
25    /// $$f(x) = \sum_{i=0}^n \lambda_i x^i$$
26    /// then the absolute value of the coefficients of any factor of \(f\) are bounded by
27    /// $${n \choose \lfloor n/2 \rfloor} \max \lbrace |\lambda_i| : i = 0, \dots, n \rbrace$$
28    pub fn mignotte_factor_coefficient_bound(&self) -> Option<Natural> {
29        let deg = self.degree()?;
30        let mut bound = Natural::ZERO;
31        for coeff in self.coeffs() {
32            bound += Abs::abs(coeff);
33        }
34        bound *= choose(Natural::from(deg), Natural::from(deg / 2));
35        Some(bound)
36    }
37
38    //https://en.wikipedia.org/wiki/Geometrical_properties_of_polynomial_roots#Lagrange's_and_Cauchy's_bounds
39    pub fn cauchys_root_bound(&self) -> Option<Rational> {
40        let d = self.degree()?;
41        if d == 0 {
42            None
43        } else {
44            Some(
45                Rational::ONE
46                    + (0..d)
47                        .map(|i| {
48                            Rational::from_integers(self.coeff(i).as_ref(), self.coeff(d).as_ref())
49                                .abs()
50                        })
51                        .max()
52                        .unwrap(),
53            )
54        }
55    }
56}
57
58// #[derive(Debug, Clone, PartialEq, Eq)]
59// struct IrreducibleIntegerMultiPolynomialStructure {}
60
61// impl Signature for IrreducibleIntegerMultiPolynomialStructure {}
62
63// impl SetSignature for IrreducibleIntegerMultiPolynomialStructure {
64//     type Set = MultiPolynomial<Integer>;
65
66//     fn is_element(&self, x: &Self::Set) -> bool {
67//         todo!()
68//     }
69// }
70
71// impl EqSignature for IrreducibleIntegerMultiPolynomialStructure {
72//     fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
73//         Integer::structure().multivariable_polynomials().equal(a, b)
74//     }
75// }
76
77// impl OrdSignature for IrreducibleIntegerMultiPolynomialStructure {
78//     fn cmp(&self, a: &Self::Set, b: &Self::Set) -> Ordering {
79//         todo!()
80//     }
81// }
82
83// impl<B: BorrowedStructure<IntegerCanonicalStructure> + 'static> UniqueFactorizationSignature
84//     for MultiPolynomialStructure<IntegerCanonicalStructure, B>
85// {
86//     type Irreducibles = IrreducibleIntegerMultiPolynomialStructure;
87
88//     type Factorizations<SelfB: BorrowedStructure<Self>> = FactoredRingElementStructure<Self, SelfB>;
89
90//     fn factorizations<'a>(&'a self) -> Self::Factorizations<&'a Self> {
91//         FactoredRingElementStructure::new(self)
92//     }
93
94//     fn into_factorizations(self) -> Self::Factorizations<Self> {
95//         FactoredRingElementStructure::new(self)
96//     }
97
98//     fn irreducibles(&self) -> impl std::borrow::Borrow<Self::Irreducibles> {
99//         IrreducibleIntegerMultiPolynomialStructure {}
100//     }
101// }
102
103// impl<B: BorrowedStructure<IntegerCanonicalStructure> + 'static> UniqueFactorizationSignature
104//     for MultiPolynomialStructure<PolynomialStructure<IntegerCanonicalStructure, B>, B>
105// {
106
107// }
108
109impl<B: BorrowedStructure<IntegerCanonicalStructure> + 'static> FactoringMonoidSignature
110    for MultiPolynomialStructure<IntegerCanonicalStructure, B>
111{
112    fn factor_unchecked(&self, p: &Self::Set) -> Factored<Self::Set, Natural> {
113        self.factor_by_yuns_and_kroneckers_inductively(
114            Rc::new(Integer::factor),
115            Rc::new(Polynomial::factor),
116            p,
117        )
118    }
119}
120
121#[cfg(test)]
122mod tests {
123    use algebraeon_sets::structure::EqSignature;
124    use berlekamp_zassenhaus::*;
125
126    use crate::structure::IntoErgonomic;
127
128    use super::*;
129
130    #[test]
131    fn test_zassenhaus_against_kroneckers() {
132        let x = &Polynomial::<Integer>::var().into_ergonomic();
133
134        let f =
135            ((2 * x.pow(3) + 6 * x.pow(2) - 4) * (6 * x.pow(5) + 7 * x.pow(4) - 4)).into_verbose();
136        let fs = Integer::structure()
137            .polynomials()
138            .factorize_by_kroneckers_method(f.clone(), Integer::factor);
139        println!("{}", f);
140        // println!("{}", f.clone().factorize_by_kroneckers_method().unwrap());
141        // println!("{}", f.clone().factorize_by_zassenhaus_algorithm().unwrap());
142        assert!(Polynomial::<Integer>::structure().factorizations().equal(
143            &fs,
144            &factorize_by_berlekamp_zassenhaus_algorithm_naive(f.clone())
145        ));
146        assert!(
147            Polynomial::<Integer>::structure()
148                .factorizations()
149                .equal(&fs, &factorize_by_berlekamp_zassenhaus_algorithm(f.clone()))
150        );
151
152        let f = (49 * x.pow(2) - 10000).into_verbose();
153        let fs = Integer::structure()
154            .polynomials()
155            .factorize_by_kroneckers_method(f.clone(), Integer::factor);
156        println!("{}", f);
157        // println!("{}", f.clone().factorize_by_kroneckers_method().unwrap());
158        // println!("{}", f.clone().factorize_by_zassenhaus_algorithm().unwrap());
159        assert!(Polynomial::<Integer>::structure().factorizations().equal(
160            &fs,
161            &factorize_by_berlekamp_zassenhaus_algorithm_naive(f.clone())
162        ));
163        assert!(
164            Polynomial::<Integer>::structure()
165                .factorizations()
166                .equal(&fs, &factorize_by_berlekamp_zassenhaus_algorithm(f.clone()))
167        );
168    }
169}
algebraeon_rings/integer/polynomial.rs

algebraeon_rings/integer/
polynomial.rs
