algebraeon_rings/finite_fields/
extension.rs

1use crate::{polynomial::*, structure::*};
2use algebraeon_nzq::*;
3use algebraeon_sets::structure::*;
4use itertools::Itertools;
5
6use super::modulo::ModuloCanonicalStructure;
7
8impl<
9    FS: FiniteFieldSignature,
10    FSB: BorrowedStructure<FS>,
11    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
12    B: BorrowedStructure<PolynomialQuotientRingStructure<FS, FSB, FSPB, true>>,
13> CountableSetSignature
14    for MultiplicativeMonoidUnitsStructure<PolynomialQuotientRingStructure<FS, FSB, FSPB, true>, B>
15{
16    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
17        self.list_all_elements().into_iter()
18    }
19}
20
21impl<
22    FS: FiniteFieldSignature,
23    FSB: BorrowedStructure<FS>,
24    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
25    B: BorrowedStructure<PolynomialQuotientRingStructure<FS, FSB, FSPB, true>>,
26> FiniteSetSignature
27    for MultiplicativeMonoidUnitsStructure<PolynomialQuotientRingStructure<FS, FSB, FSPB, true>, B>
28{
29    fn list_all_elements(&self) -> Vec<Self::Set> {
30        let mut all_base_elements = vec![self.monoid().ring().coeff_ring().zero()];
31        for unit in self.monoid().ring().coeff_ring().all_units() {
32            all_base_elements.push(unit);
33        }
34
35        let mut all_base_elements_product = (0..self.monoid().degree())
36            .map(|_| &all_base_elements)
37            .multi_cartesian_product();
38
39        // Pop the all-zeros element
40        all_base_elements_product.next().unwrap();
41
42        // What remains is the coefficients for all non-zero elements in self
43        all_base_elements_product
44            .map(|coeffs| {
45                self.monoid().ring().reduce_poly(Polynomial::from_coeffs(
46                    coeffs.into_iter().cloned().collect(),
47                ))
48            })
49            .collect()
50    }
51}
52
53impl<
54    FS: FiniteFieldSignature,
55    FSB: BorrowedStructure<FS>,
56    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
57> FiniteFieldSignature for PolynomialQuotientRingStructure<FS, FSB, FSPB, true>
58{
59    fn characteristic_and_power(&self) -> (Natural, Natural) {
60        let (p, t) = self.ring().coeff_ring().characteristic_and_power();
61        let d = Natural::from(self.degree());
62        (p, d * t)
63    }
64}
65
66pub fn new_finite_field_extension<FS: FiniteFieldSignature>(
67    finite_field: FS,
68    poly: Polynomial<FS::Set>,
69) -> PolynomialQuotientRingStructure<FS, FS, PolynomialStructure<FS, FS>, true>
70where
71    PolynomialStructure<FS, FS>: FactoringMonoidSignature<Set = Polynomial<FS::Set>>,
72{
73    finite_field
74        .into_polynomials()
75        .into_quotient_field_unchecked(poly)
76}
77
78#[allow(unused)]
79pub(crate) fn f9() -> PolynomialQuotientRingStructure<
80    ModuloCanonicalStructure<3>,
81    ModuloCanonicalStructure<3>,
82    PolynomialStructure<ModuloCanonicalStructure<3>, ModuloCanonicalStructure<3>>,
83    true,
84> {
85    use crate::finite_fields::modulo::*;
86    new_finite_field_extension::<ModuloCanonicalStructure<3>>(
87        Modulo::<3>::structure(),
88        Polynomial::from_coeffs(vec![1, 1, 2]),
89    )
90}
91
92#[cfg(test)]
93mod tests {
94
95    use super::*;
96
97    #[test]
98    fn test_f9_elements() {
99        let f9 = f9();
100
101        let (p, t) = f9.characteristic_and_power();
102        assert_eq!(p, 3u32.into());
103        assert_eq!(t, 2u32.into());
104
105        let mut c = 0;
106        for x in f9.list_all_elements() {
107            println!("{:?}", x);
108            c += 1;
109        }
110        assert_eq!(c, 9);
111    }
112}
algebraeon_rings/finite_fields/extension.rs

algebraeon_rings/finite_fields/
extension.rs
