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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use super::cantor_zassenhaus;
use crate::algorithms::poly_gcd::finite::poly_squarefree_part_finite_field;
use crate::computation::ComputationController;
use crate::divisibility::*;
use crate::field::*;
use crate::homomorphism::SelfIso;
use crate::integer::*;
use crate::pid::*;
use crate::ring::*;
use crate::rings::finite::*;
use crate::rings::poly::*;

/// Factors a polynomial with coefficients in a finite field.
#[stability::unstable(feature = "enable")]
pub fn poly_factor_finite_field<P, Controller>(
    poly_ring: P,
    f: &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 as RingStore>::Type: FiniteRing + Field + SelfIso,
    Controller: ComputationController,
{
    assert!(!poly_ring.is_zero(f));
    let even_char = BigIntRing::RING.is_even(&poly_ring.base_ring().characteristic(&BigIntRing::RING).unwrap());

    controller.run_computation(
        format_args!("factor_poly_GF(deg={})", poly_ring.degree(f).unwrap()),
        |controller| {
            let mut result = Vec::new();
            let mut unit = poly_ring.base_ring().one();
            let mut el = poly_ring.clone_el(f);

            // we repeatedly remove the square-free part
            while !poly_ring.is_unit(&el) {
                let sqrfree_part = poly_squarefree_part_finite_field(&poly_ring, &el, controller.clone());
                assert!(!poly_ring.is_unit(&sqrfree_part));

                // factor the square-free part into distinct-degree factors
                let distinct_degree_factors = cantor_zassenhaus::distinct_degree_factorization(
                    &poly_ring,
                    poly_ring.clone_el(&sqrfree_part),
                    controller.clone(),
                );
                for (d, factor_d) in distinct_degree_factors.into_iter().enumerate() {
                    let mut stack = Vec::new();
                    stack.push(factor_d);

                    // and finally extract each individual factor
                    while let Some(mut current) = stack.pop() {
                        current = poly_ring.normalize(current);

                        if poly_ring.is_one(&current) {
                            continue;
                        } else if poly_ring.degree(&current) == Some(d) {
                            // add to result
                            let mut found = false;
                            for (factor, power) in &mut result {
                                if poly_ring.eq_el(factor, &current) {
                                    *power += 1;
                                    found = true;
                                    break;
                                }
                            }
                            if !found {
                                result.push((current, 1));
                            }
                        } else if even_char {
                            let factor = cantor_zassenhaus::cantor_zassenhaus_even(
                                &poly_ring,
                                poly_ring.clone_el(&current),
                                d,
                                controller.clone(),
                            );
                            stack.push(poly_ring.checked_div(&current, &factor).unwrap());
                            stack.push(factor);
                        } else {
                            let factor = cantor_zassenhaus::cantor_zassenhaus(
                                &poly_ring,
                                poly_ring.clone_el(&current),
                                d,
                                controller.clone(),
                            );
                            stack.push(poly_ring.checked_div(&current, &factor).unwrap());
                            stack.push(factor);
                        }
                    }
                }
                el = poly_ring.checked_div(&el, &sqrfree_part).unwrap();
            }
            poly_ring
                .base_ring()
                .mul_assign_ref(&mut unit, poly_ring.coefficient_at(&el, 0));
            debug_assert!(poly_ring.base_ring().is_unit(&unit));

            return (result, unit);
        },
    )
}