algebraeon_rings/polynomial/
quotient.rs

1use super::{Polynomial, polynomial_structure::*};
2use crate::{matrix::*, structure::*};
3use algebraeon_nzq::{Integer, Natural};
4use algebraeon_sets::structure::*;
5use std::borrow::{Borrow, Cow};
6
7pub type PolynomialQuotientRingStructure<FS, FSB, FSPB, const IS_FIELD: bool> =
8    EuclideanRemainderQuotientStructure<PolynomialStructure<FS, FSB>, FSPB, IS_FIELD>;
9
10impl<
11    FS: FieldSignature + CharacteristicSignature,
12    FSB: BorrowedStructure<FS>,
13    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
14    const IS_FIELD: bool,
15> CharacteristicSignature for PolynomialQuotientRingStructure<FS, FSB, FSPB, IS_FIELD>
16where
17    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
18{
19    fn characteristic(&self) -> Natural {
20        self.ring().characteristic()
21    }
22}
23
24impl<
25    FS: FieldSignature + CharZeroRingSignature,
26    FSB: BorrowedStructure<FS>,
27    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
28    const IS_FIELD: bool,
29> CharZeroRingSignature for PolynomialQuotientRingStructure<FS, FSB, FSPB, IS_FIELD>
30where
31    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
32{
33    fn try_to_int(&self, x: &Self::Set) -> Option<Integer> {
34        let x_reduced = self.reduce(x);
35        self.ring().try_to_int(&x_reduced)
36    }
37}
38
39impl<
40    FS: FieldSignature,
41    FSB: BorrowedStructure<FS>,
42    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
43    const IS_FIELD: bool,
44> PolynomialQuotientRingStructure<FS, FSB, FSPB, IS_FIELD>
45where
46    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
47{
48    pub fn coefficient_ring_inclusion(
49        &self,
50    ) -> PolynomialQuotientRingExtension<FS, FSB, FSPB, IS_FIELD> {
51        PolynomialQuotientRingExtension::new(self.clone())
52    }
53
54    pub fn into_coefficient_ring_inclusion(
55        self,
56    ) -> PolynomialQuotientRingExtension<FS, FSB, FSPB, IS_FIELD> {
57        PolynomialQuotientRingExtension::new(self)
58    }
59}
60
61impl<
62    FS: FieldSignature,
63    FSB: BorrowedStructure<FS>,
64    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
65    const IS_FIELD: bool,
66> PolynomialQuotientRingStructure<FS, FSB, FSPB, IS_FIELD>
67where
68    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
69{
70    pub fn generator(&self) -> Polynomial<FS::Set> {
71        self.ring().var()
72    }
73
74    pub fn col_multiplication_matrix(&self, a: &Polynomial<FS::Set>) -> Matrix<FS::Set> {
75        self.coefficient_ring_inclusion()
76            .col_multiplication_matrix(a)
77    }
78
79    pub fn row_multiplication_matrix(&self, a: &Polynomial<FS::Set>) -> Matrix<FS::Set> {
80        self.coefficient_ring_inclusion()
81            .row_multiplication_matrix(a)
82    }
83
84    pub fn to_col(&self, a: &Polynomial<FS::Set>) -> Matrix<FS::Set> {
85        self.coefficient_ring_inclusion()
86            .range_module_structure()
87            .to_col(a)
88    }
89
90    pub fn to_row(&self, a: &Polynomial<FS::Set>) -> Matrix<FS::Set> {
91        self.coefficient_ring_inclusion()
92            .range_module_structure()
93            .to_row(a)
94    }
95
96    pub fn to_vec(&self, a: &Polynomial<FS::Set>) -> Vec<FS::Set> {
97        self.coefficient_ring_inclusion()
98            .range_module_structure()
99            .to_vec(a)
100    }
101
102    pub fn from_col(&self, v: Matrix<FS::Set>) -> Polynomial<FS::Set> {
103        self.coefficient_ring_inclusion()
104            .range_module_structure()
105            .from_col(v)
106    }
107
108    pub fn from_row(&self, v: Matrix<FS::Set>) -> Polynomial<FS::Set> {
109        self.coefficient_ring_inclusion()
110            .range_module_structure()
111            .from_row(v)
112    }
113
114    pub fn from_vec(&self, v: Vec<impl Borrow<FS::Set>>) -> Polynomial<FS::Set> {
115        self.coefficient_ring_inclusion()
116            .range_module_structure()
117            .from_vec(v)
118    }
119
120    pub fn degree(&self) -> usize {
121        self.ring().degree(self.modulus()).unwrap()
122    }
123}
124
125impl<
126    FS: FieldSignature,
127    FSB: BorrowedStructure<FS>,
128    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
129> PolynomialQuotientRingStructure<FS, FSB, FSPB, true>
130where
131    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
132{
133    pub fn min_poly(&self, a: &Polynomial<FS::Set>) -> Polynomial<FS::Set> {
134        self.coefficient_ring_inclusion().min_poly(a)
135    }
136
137    pub fn norm(&self, a: &Polynomial<FS::Set>) -> FS::Set {
138        self.coefficient_ring_inclusion().norm(a)
139    }
140
141    pub fn trace(&self, a: &Polynomial<FS::Set>) -> FS::Set {
142        self.coefficient_ring_inclusion().trace(a)
143    }
144}
145
146impl<
147    const IS_FIELD: bool,
148    FS: FieldSignature + FiniteSetSignature,
149    FSB: BorrowedStructure<FS>,
150    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
151> CountableSetSignature for PolynomialQuotientRingStructure<FS, FSB, FSPB, IS_FIELD>
152where
153    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
154{
155    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
156        self.coefficient_ring_inclusion()
157            .range_module_structure()
158            .generate_all_elements()
159            .collect::<Vec<_>>()
160            .into_iter()
161    }
162}
163
164impl<
165    const IS_FIELD: bool,
166    FS: FieldSignature + FiniteSetSignature,
167    FSB: BorrowedStructure<FS>,
168    FSPB: BorrowedStructure<PolynomialStructure<FS, FSB>>,
169> FiniteSetSignature for PolynomialQuotientRingStructure<FS, FSB, FSPB, IS_FIELD>
170where
171    PolynomialStructure<FS, FSB>: SetSignature<Set = Polynomial<FS::Set>>,
172{
173}
174
175#[derive(Debug, Clone, PartialEq, Eq)]
176pub struct PolynomialQuotientRingExtension<
177    Field: FieldSignature,
178    FieldB: BorrowedStructure<Field>,
179    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
180    const IS_FIELD: bool,
181> {
182    polynomial_quotient_ring: PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD>,
183}
184
185impl<
186    Field: FieldSignature,
187    FieldB: BorrowedStructure<Field>,
188    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
189    const IS_FIELD: bool,
190> PolynomialQuotientRingExtension<Field, FieldB, FieldPolyB, IS_FIELD>
191{
192    pub fn new(
193        polynomial_quotient_ring: PolynomialQuotientRingStructure<
194            Field,
195            FieldB,
196            FieldPolyB,
197            IS_FIELD,
198        >,
199    ) -> Self {
200        Self {
201            polynomial_quotient_ring,
202        }
203    }
204}
205
206impl<
207    Field: FieldSignature,
208    FieldB: BorrowedStructure<Field>,
209    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
210    const IS_FIELD: bool,
211> Morphism<Field, PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD>>
212    for PolynomialQuotientRingExtension<Field, FieldB, FieldPolyB, IS_FIELD>
213{
214    fn domain(&self) -> &Field {
215        self.polynomial_quotient_ring.ring().coeff_ring()
216    }
217
218    fn range(&self) -> &PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD> {
219        &self.polynomial_quotient_ring
220    }
221}
222
223impl<
224    Field: FieldSignature,
225    FieldB: BorrowedStructure<Field>,
226    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
227    const IS_FIELD: bool,
228> Function<Field, PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD>>
229    for PolynomialQuotientRingExtension<Field, FieldB, FieldPolyB, IS_FIELD>
230{
231    fn image(&self, x: &Field::Set) -> Polynomial<Field::Set> {
232        Polynomial::constant(x.clone())
233    }
234}
235
236impl<
237    Field: FieldSignature,
238    FieldB: BorrowedStructure<Field>,
239    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
240    const IS_FIELD: bool,
241> RingHomomorphism<Field, PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD>>
242    for PolynomialQuotientRingExtension<Field, FieldB, FieldPolyB, IS_FIELD>
243{
244}
245
246impl<
247    Field: FieldSignature,
248    FieldB: BorrowedStructure<Field>,
249    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
250    const IS_FIELD: bool,
251> InjectiveFunction<Field, PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD>>
252    for PolynomialQuotientRingExtension<Field, FieldB, FieldPolyB, IS_FIELD>
253{
254    fn try_preimage(&self, x: &Polynomial<Field::Set>) -> Option<Field::Set> {
255        self.domain()
256            .polynomials()
257            .as_constant(&self.range().reduce(x))
258    }
259}
260
261impl<
262    'h,
263    Field: FieldSignature,
264    FieldB: BorrowedStructure<Field>,
265    FieldPolyB: BorrowedStructure<PolynomialStructure<Field, FieldB>>,
266    const IS_FIELD: bool,
267> FreeModuleSignature<Field>
268    for RingHomomorphismRangeModuleStructure<
269        'h,
270        Field,
271        PolynomialQuotientRingStructure<Field, FieldB, FieldPolyB, IS_FIELD>,
272        PolynomialQuotientRingExtension<Field, FieldB, FieldPolyB, IS_FIELD>,
273    >
274{
275    type Basis = EnumeratedFiniteSetStructure;
276
277    fn basis_set(&self) -> impl std::borrow::Borrow<Self::Basis> {
278        Self::Basis::new(self.module().degree())
279    }
280
281    fn to_component<'a>(&self, b: &usize, v: &'a Polynomial<Field::Set>) -> Cow<'a, Field::Set> {
282        Cow::Owned(
283            self.ring()
284                .polynomials()
285                .coeff(&self.module().reduce(v), *b)
286                .into_owned(),
287        )
288    }
289
290    fn from_component(&self, b: &usize, r: &Field::Set) -> Polynomial<Field::Set> {
291        self.ring().polynomials().constant_var_pow(r.clone(), *b)
292    }
293}
294
295#[cfg(test)]
296mod tests {
297    use super::*;
298    use algebraeon_nzq::Rational;
299    use std::str::FromStr;
300
301    #[test]
302    fn finite_dimensional_field_extension_structure() {
303        let x = Rational::structure()
304            .into_polynomials()
305            .var()
306            .into_ergonomic();
307        {
308            let p = (x.pow(3) + &x - 1).into_verbose();
309            let f = p.algebraic_number_field().unwrap();
310            let ext = PolynomialQuotientRingExtension::new(f);
311            assert_eq!(ext.degree(), 3);
312            assert_eq!(
313                ext.image(&Rational::from_str("4").unwrap()),
314                (4 * x.pow(0)).into_verbose()
315            );
316            assert_eq!(ext.try_preimage(&(3 * x.pow(2) + 1).into_verbose()), None);
317            assert_eq!(
318                ext.try_preimage(&(x.pow(3) + &x + 1).into_verbose()),
319                Some(Rational::from_str("2").unwrap())
320            );
321
322            assert_eq!(
323                ext.norm(&(5 * x.pow(1) + 2).into_verbose()),
324                Rational::from_str("183").unwrap()
325            );
326        }
327        {
328            // Z[i]
329            let p = (x.pow(2) + 1).into_verbose();
330            let f = p.algebraic_number_field().unwrap();
331            let ext = PolynomialQuotientRingExtension::new(f);
332            assert_eq!(ext.degree(), 2);
333            // a^2 + b^2
334            assert_eq!(
335                ext.norm(&(3 + 4 * &x).into_verbose()),
336                Rational::from_str("25").unwrap()
337            );
338            // 2a
339            assert_eq!(
340                ext.trace(&(3 + 4 * &x).into_verbose()),
341                Rational::from_str("6").unwrap()
342            );
343            // min_poly(1+i) = x^2 - 2x + 2
344            assert_eq!(
345                ext.min_poly(&(1 + &x).into_verbose()),
346                (x.pow(2) - 2 * &x + 2).into_verbose()
347            );
348        }
349    }
350}
algebraeon_rings/polynomial/quotient.rs

algebraeon_rings/polynomial/
quotient.rs
