algebraeon_rings/finite_fields/
conway_finite_fields.rs

1use super::conway_polynomials::conway_polynomial;
2use crate::{
3    matrix::{Matrix, MatrixStructure},
4    polynomial::*,
5    structure::*,
6};
7use algebraeon_nzq::{Integer, IntegerCanonicalStructure, Natural};
8use algebraeon_sets::structure::*;
9
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct ConwayFiniteFieldStructure {
12    p: usize,
13    n: usize,
14    structure: PolynomialQuotientRingStructure<
15        EuclideanRemainderQuotientStructure<
16            IntegerCanonicalStructure,
17            IntegerCanonicalStructure,
18            true,
19        >,
20        EuclideanRemainderQuotientStructure<
21            IntegerCanonicalStructure,
22            IntegerCanonicalStructure,
23            true,
24        >,
25        PolynomialStructure<
26            EuclideanRemainderQuotientStructure<
27                IntegerCanonicalStructure,
28                IntegerCanonicalStructure,
29                true,
30            >,
31            EuclideanRemainderQuotientStructure<
32                IntegerCanonicalStructure,
33                IntegerCanonicalStructure,
34                true,
35            >,
36        >,
37        true,
38    >,
39}
40
41impl ConwayFiniteFieldStructure {
42    pub fn new(p: usize, n: usize) -> Result<Self, ()> {
43        let f = conway_polynomial(p, n)?;
44        Ok(Self {
45            p,
46            n,
47            structure: Integer::structure()
48                .into_quotient_field_unchecked(Integer::from(p))
49                .into_polynomials()
50                .into_quotient_field_unchecked(f.clone()),
51        })
52    }
53
54    pub fn reduce(&self, f: Polynomial<Integer>) -> Polynomial<Integer> {
55        self.structure.reduce(f)
56    }
57
58    pub fn to_row_vector(&self, f: &Polynomial<Integer>) -> Matrix<Integer> {
59        self.structure.to_row(f)
60    }
61
62    pub fn to_col_vector(&self, f: &Polynomial<Integer>) -> Matrix<Integer> {
63        self.structure.to_col(f)
64    }
65
66    pub fn to_vector(&self, f: &Polynomial<Integer>) -> Vec<Integer> {
67        self.structure.to_vec(f)
68    }
69
70    pub fn from_row_vector(&self, v: Matrix<Integer>) -> Polynomial<Integer> {
71        self.structure.from_row(v)
72    }
73
74    pub fn from_col_vector(&self, v: Matrix<Integer>) -> Polynomial<Integer> {
75        self.structure.from_col(v)
76    }
77
78    pub fn from_vector(&self, v: Vec<Integer>) -> Polynomial<Integer> {
79        self.structure.from_vec(v)
80    }
81}
82
83impl Signature for ConwayFiniteFieldStructure {}
84
85impl SetSignature for ConwayFiniteFieldStructure {
86    type Set = Polynomial<Integer>;
87
88    fn is_element(&self, _: &Self::Set) -> Result<(), String> {
89        Ok(())
90    }
91}
92
93impl EqSignature for ConwayFiniteFieldStructure {
94    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
95        self.structure.equal(a, b)
96    }
97}
98
99impl RinglikeSpecializationSignature for ConwayFiniteFieldStructure {}
100
101impl ZeroSignature for ConwayFiniteFieldStructure {
102    fn zero(&self) -> Self::Set {
103        self.structure.zero()
104    }
105}
106
107impl AdditionSignature for ConwayFiniteFieldStructure {
108    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
109        self.structure.add(a, b)
110    }
111}
112
113impl CancellativeAdditionSignature for ConwayFiniteFieldStructure {
114    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
115        Some(self.sub(a, b))
116    }
117}
118
119impl TryNegateSignature for ConwayFiniteFieldStructure {
120    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
121        Some(self.neg(a))
122    }
123}
124
125impl AdditiveMonoidSignature for ConwayFiniteFieldStructure {}
126
127impl AdditiveGroupSignature for ConwayFiniteFieldStructure {
128    fn neg(&self, a: &Self::Set) -> Self::Set {
129        self.structure.neg(a)
130    }
131}
132
133impl OneSignature for ConwayFiniteFieldStructure {
134    fn one(&self) -> Self::Set {
135        self.structure.one()
136    }
137}
138
139impl MultiplicationSignature for ConwayFiniteFieldStructure {
140    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
141        self.structure.mul(a, b)
142    }
143}
144
145impl CommutativeMultiplicationSignature for ConwayFiniteFieldStructure {}
146
147impl MultiplicativeMonoidSignature for ConwayFiniteFieldStructure {}
148
149impl MultiplicativeAbsorptionMonoidSignature for ConwayFiniteFieldStructure {}
150
151impl LeftDistributiveMultiplicationOverAddition for ConwayFiniteFieldStructure {}
152
153impl RightDistributiveMultiplicationOverAddition for ConwayFiniteFieldStructure {}
154
155impl SemiRingSignature for ConwayFiniteFieldStructure {}
156
157impl RingSignature for ConwayFiniteFieldStructure {
158    fn is_reduced(&self) -> Result<bool, String> {
159        Ok(true)
160    }
161}
162
163impl CountableSetSignature for ConwayFiniteFieldStructure {
164    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
165        self.all_units_and_zero().into_iter()
166    }
167}
168
169impl FiniteSetSignature for ConwayFiniteFieldStructure {}
170
171impl CharacteristicSignature for ConwayFiniteFieldStructure {
172    fn characteristic(&self) -> Natural {
173        self.characteristic_and_power().0
174    }
175}
176
177impl TryReciprocalSignature for ConwayFiniteFieldStructure {
178    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
179        self.structure.try_reciprocal(a)
180    }
181}
182
183impl CancellativeMultiplicationSignature for ConwayFiniteFieldStructure {
184    fn try_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
185        self.structure.try_divide(a, b)
186    }
187}
188
189impl MultiplicativeIntegralMonoidSignature for ConwayFiniteFieldStructure {}
190
191impl IntegralDomainSignature for ConwayFiniteFieldStructure {}
192
193impl FieldSignature for ConwayFiniteFieldStructure {}
194
195impl<B: BorrowedStructure<ConwayFiniteFieldStructure>> CountableSetSignature
196    for MultiplicativeMonoidUnitsStructure<ConwayFiniteFieldStructure, B>
197{
198    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
199        self.list_all_elements().into_iter()
200    }
201}
202
203impl<B: BorrowedStructure<ConwayFiniteFieldStructure>> FiniteSetSignature
204    for MultiplicativeMonoidUnitsStructure<ConwayFiniteFieldStructure, B>
205{
206    fn list_all_elements(&self) -> Vec<Self::Set> {
207        self.monoid().structure.all_units()
208    }
209}
210
211impl FiniteFieldSignature for ConwayFiniteFieldStructure {
212    fn characteristic_and_power(&self) -> (Natural, Natural) {
213        (self.p.into(), self.n.into())
214    }
215}
216
217#[derive(Debug, Clone)]
218pub struct ConwayFiniteFieldInclusion {
219    // a prime
220    #[allow(unused)]
221    p: usize,
222    // finite field of order p^m
223    domain: ConwayFiniteFieldStructure,
224    // finite field of order p^n
225    range: ConwayFiniteFieldStructure,
226    // n/m
227    #[allow(unused)]
228    degree: usize,
229    // Linear map F_{p^m} -> F_{p^n} of column vectors of polynomial coefficients over F_p
230    inclusion: Matrix<Integer>,
231    // matrices modulo p
232    mat_mod_p: MatrixStructure<
233        EuclideanRemainderQuotientStructure<
234            IntegerCanonicalStructure,
235            IntegerCanonicalStructure,
236            true,
237        >,
238        EuclideanRemainderQuotientStructure<
239            IntegerCanonicalStructure,
240            IntegerCanonicalStructure,
241            true,
242        >,
243    >,
244}
245
246impl ConwayFiniteFieldInclusion {
247    pub fn new(p: usize, m: usize, n: usize) -> Result<Self, &'static str> {
248        if n.is_multiple_of(m) {
249            let degree = n / m;
250
251            let domain = ConwayFiniteFieldStructure::new(p, m).unwrap();
252            let range = ConwayFiniteFieldStructure::new(p, n).unwrap();
253
254            // r = (p^n-1)/(p^m-1)
255            let r = (Natural::from(p).pow(&n.into()) - Natural::ONE)
256                / (Natural::from(p).pow(&m.into()) - Natural::ONE);
257
258            // x -> x^r
259            let inclusion = Matrix::join_cols(
260                n,
261                (0..m)
262                    .map(|i| range.to_col_vector(&range.nat_pow(&Polynomial::var_pow(i), &r)))
263                    .collect(),
264            );
265            assert_eq!(inclusion.rows(), n);
266            assert_eq!(inclusion.cols(), m);
267            Ok(Self {
268                p,
269                domain,
270                range,
271                degree,
272                inclusion,
273                mat_mod_p: MatrixStructure::new(
274                    Integer::structure()
275                        .into_quotient_field(p.into())
276                        .map_err(|_| "p not prime")
277                        .unwrap(),
278                ),
279            })
280        } else {
281            Err("m must divide n")
282        }
283    }
284}
285
286impl Morphism<ConwayFiniteFieldStructure, ConwayFiniteFieldStructure>
287    for ConwayFiniteFieldInclusion
288{
289    fn domain(&self) -> &ConwayFiniteFieldStructure {
290        &self.domain
291    }
292
293    fn range(&self) -> &ConwayFiniteFieldStructure {
294        &self.range
295    }
296}
297
298impl Function<ConwayFiniteFieldStructure, ConwayFiniteFieldStructure>
299    for ConwayFiniteFieldInclusion
300{
301    fn image(&self, x: &Polynomial<Integer>) -> Polynomial<Integer> {
302        self.range().from_col_vector(
303            self.mat_mod_p
304                .mul(&self.inclusion, &self.domain().to_col_vector(x))
305                .unwrap(),
306        )
307    }
308}
309
310impl InjectiveFunction<ConwayFiniteFieldStructure, ConwayFiniteFieldStructure>
311    for ConwayFiniteFieldInclusion
312{
313    fn try_preimage(&self, x: &Polynomial<Integer>) -> Option<Polynomial<Integer>> {
314        Some(
315            self.domain().from_vector(
316                self.inclusion
317                    .clone()
318                    .col_solve(&self.range().to_vector(x))?,
319            ),
320        )
321    }
322}
323
324impl RingHomomorphism<ConwayFiniteFieldStructure, ConwayFiniteFieldStructure>
325    for ConwayFiniteFieldInclusion
326{
327}
328
329// #[derive(Debug, Clone, PartialEq, Eq)]
330// pub struct ConwayFiniteFieldInclusionStructure {
331//     p: Natural,
332// }
333// impl ConwayFiniteFieldInclusionStructure {
334//     pub fn new(p: Natural) -> Self {
335//         debug_assert!(is_prime(&p));
336//         Self { p }
337//     }
338// }
339
340// impl Structure for ConwayFiniteFieldInclusionStructure {}
341
342// impl SetStructure for ConwayFiniteFieldInclusionStructure {
343//     type Set = ConwayFiniteFieldInclusion;
344
345//     fn is_element(&self, x: &Self::Set) -> bool {
346//         self.p == x.p
347//     }
348// }
349
350// impl MorphismsStructure<ConwayFiniteFieldStructure, ConwayFiniteFieldStructure>
351//     for ConwayFiniteFieldInclusionStructure
352// {
353// }
354
355#[cfg(test)]
356mod tests {
357    use super::*;
358
359    #[test]
360    fn conway_finite_fields_homomorphism() {
361        let f = ConwayFiniteFieldInclusion::new(2, 2, 4).unwrap();
362
363        f.inclusion.pprint();
364
365        let a = Polynomial::var();
366        println!("a = {}", a);
367        let b = f.image(&a.clone());
368        println!("b = {}", b);
369
370        assert!(
371            f.domain()
372                .equal(&f.domain().nat_pow(&a, &3u32.into()), &f.domain().one())
373        );
374        assert!(
375            f.range()
376                .equal(&f.range().nat_pow(&b, &3u32.into()), &f.range().one())
377        );
378
379        let a2 = f.try_preimage(&b).unwrap();
380        println!("a2 = {}", a2);
381        assert!(f.domain().equal(&a, &a2));
382    }
383
384    #[test]
385    fn conway_finite_fields_compatibility() {
386        /*
387                 x
388        f_{3^2} ===> f_{3^4}
389           ||           ||
390         y ||           || z
391           \/           \/
392        f_{3^6} ===> f_{3^12}
393                 w
394
395        */
396
397        let f_3_2 = ConwayFiniteFieldStructure::new(3, 2).unwrap();
398        let f_3_12 = ConwayFiniteFieldStructure::new(3, 12).unwrap();
399
400        let x = ConwayFiniteFieldInclusion::new(3, 2, 4).unwrap();
401        let y = ConwayFiniteFieldInclusion::new(3, 2, 6).unwrap();
402        let z = ConwayFiniteFieldInclusion::new(3, 4, 12).unwrap();
403        let w = ConwayFiniteFieldInclusion::new(3, 6, 12).unwrap();
404
405        for a in f_3_2.list_all_elements() {
406            assert!(f_3_12.equal(&z.image(&x.image(&a)), &w.image(&y.image(&a))));
407        }
408    }
409}
algebraeon_rings/finite_fields/conway_finite_fields.rs

algebraeon_rings/finite_fields/
conway_finite_fields.rs
