feanor_math/rings/extension/
galois_field.rs

1use std::alloc::{Allocator, Global};
2use std::marker::PhantomData;
3
4use extension_impl::FreeAlgebraImplBase;
5use sparse::SparseMapVector;
6use zn_64::Zn;
7
8use crate::algorithms::convolution::*;
9use crate::algorithms::eea::signed_gcd;
10use crate::algorithms::poly_gcd::finite::poly_squarefree_part_finite_field;
11use crate::algorithms::int_factor::factor;
12use crate::algorithms::int_factor::is_prime_power;
13use crate::algorithms::matmul::{ComputeInnerProduct, StrassenHint};
14use crate::algorithms::poly_gcd::PolyTFracGCDRing;
15use crate::algorithms::unity_root::*;
16use crate::computation::DontObserve;
17use crate::delegate::{DelegateRing, DelegateRingImplFiniteRing};
18use crate::divisibility::{DivisibilityRingStore, Domain};
19use crate::field::*;
20use crate::pid::PrincipalIdealRing;
21use crate::rings::extension::extension_impl::FreeAlgebraImpl;
22use crate::rings::finite::*;
23use crate::algorithms::convolution::fft::*;
24use crate::algorithms::poly_factor::cantor_zassenhaus;
25use crate::pid::EuclideanRing;
26use crate::primitive_int::{StaticRing, StaticRingBase};
27use crate::rings::field::{AsField, AsFieldBase};
28use crate::rings::local::{AsLocalPIR, AsLocalPIRBase};
29use crate::rings::poly::dense_poly::DensePolyRing;
30use crate::rings::poly::PolyRing;
31use crate::rings::zn::*;
32use crate::ring::*;
33use crate::rings::extension::*;
34use crate::integer::*;
35use crate::serialization::*;
36
37use feanor_serde::newtype_struct::*;
38use serde::{Serialize, Deserialize, Deserializer, Serializer};
39use serde::de::DeserializeSeed;
40
41fn filter_irreducible<R, P>(poly_ring: P, mod_f_ring: R, degree: usize) -> Option<El<P>>
42    where P: RingStore,
43        P::Type: PolyRing + EuclideanRing,
44        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + FiniteRing + Field,
45        R: RingStore,
46        R::Type: FreeAlgebra,
47        <R::Type as RingExtension>::BaseRing: RingStore<Type = <<P::Type as RingExtension>::BaseRing as RingStore>::Type>
48{
49    let f = mod_f_ring.generating_poly(&poly_ring, &poly_ring.base_ring().identity());
50    let squarefree_part = poly_squarefree_part_finite_field(&poly_ring, &f, DontObserve);
51    if poly_ring.degree(&squarefree_part) != Some(degree) {
52        return None;
53    }
54    if !cantor_zassenhaus::squarefree_is_irreducible_base(&poly_ring, &mod_f_ring) {
55        return None;
56    }
57    return Some(mod_f_ring.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
58}
59
60///
61/// Tries to find a "small" irreducible polynomial of given degree.
62/// 
63/// "small" is not well-defined, but can mean sparse, or having a small `deg(f - lt(f))`.
64/// Both will lead to more efficient arithmetic in the ring `k[X]/(f)`. However, in general
65/// finding a very small `f` is hard, thus we use heuristics.
66/// 
67fn find_small_irreducible_poly_base<P, C>(poly_ring: P, degree: usize, convolution: C, rng: &mut oorandom::Rand64) -> El<P>
68    where P: RingStore,
69        P::Type: PolyRing + EuclideanRing,
70        <P::Type as RingExtension>::BaseRing: Copy,
71        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>,
72        C: ConvolutionAlgorithm<<<P::Type as RingExtension>::BaseRing as RingStore>::Type>
73{
74    let Fp = *poly_ring.base_ring();
75    let create_mod_f_ring = |f: &El<P>| {
76        let mut f_body = SparseMapVector::new(degree, poly_ring.base_ring());
77        for (c, i) in poly_ring.terms(f) {
78            if i != degree {
79                *f_body.at_mut(i) = poly_ring.base_ring().negate(poly_ring.base_ring().clone_el(c));
80            }
81        }
82        return FreeAlgebraImpl::new_with_convolution(Fp, degree, f_body, "θ", Global, &convolution);
83    };
84
85    if degree > 3 {
86
87        // first try trinomials, they seem to have a good chance of being irreducible
88        for _ in 0..16 {
89            let i = (StaticRing::<i64>::RING.get_uniformly_random(&(TryInto::<i64>::try_into(degree).unwrap() - 1), || rng.rand_u64()) + 1) as usize;
90            let a = Fp.random_element(|| rng.rand_u64());
91            let b = Fp.random_element(|| rng.rand_u64());
92            let f = poly_ring.from_terms([(a, 0), (b, i), (Fp.one(), degree)].into_iter());
93            if let Some(result)  = filter_irreducible(&poly_ring, create_mod_f_ring(&f), degree) {
94                return result;
95            }
96        }
97    
98        // next, check for cases where we can take `small_poly(X^high_power)`; these cases are characterized by the
99        // fact that we have `degree = small_d * large_d` with `large_d | #F_(q^small_d)*`
100        let ZZbig = BigIntRing::RING;
101        let ZZ = StaticRing::<i64>::RING;
102    
103        let p = Fp.size(&ZZbig).unwrap();
104        let mut small_d = 1;
105        let Fq_star_order = ZZbig.sub(ZZbig.pow(ZZbig.clone_el(&p), small_d as usize), ZZbig.one());
106        let mut large_d = int_cast(signed_gcd(Fq_star_order, int_cast(TryInto::<i64>::try_into(degree).unwrap() / small_d, ZZbig, StaticRing::<i64>::RING), ZZbig), ZZ, ZZbig);
107        let mut increased_small_d = true;
108        while increased_small_d {
109            increased_small_d = false;
110            // use a greedy approach, just add a factor to small_d if it makes large_d larger
111            for (k, _) in factor(&ZZ, TryInto::<i64>::try_into(degree).unwrap() / small_d) {
112                let new_small_d = small_d * k;
113                let Fq_star_order = ZZbig.sub(ZZbig.pow(ZZbig.clone_el(&p), new_small_d as usize), ZZbig.one());
114                let new_large_d = int_cast(signed_gcd(Fq_star_order, int_cast(TryInto::<i64>::try_into(degree).unwrap() / new_small_d, ZZbig, StaticRing::<i64>::RING), ZZbig), ZZ, ZZbig);
115                if new_large_d > large_d {
116                    small_d = new_small_d;
117                    large_d = new_large_d;
118                    increased_small_d = true;
119                    break;
120                }
121            }
122        }
123        small_d = TryInto::<i64>::try_into(degree).unwrap() / large_d;
124        if large_d != 1 {
125            let Fq_star_order = ZZbig.sub(ZZbig.pow(ZZbig.clone_el(&p), small_d as usize), ZZbig.one());
126            // careful here to not get an infinite generic argument recursion
127            let Fq = GaloisField::new_internal(Fp, small_d as usize, Global, &convolution);
128            // the primitive element of `Fq` clearly has no `k`-th root, for every `k | large_d` since `large_d | #Fq*`;
129            // hence we can use `MinPoly(primitive_element)(X^large_d)`
130            let primitive_element = if is_prim_root_of_unity_gen(&Fq, &Fq.canonical_gen(), &Fq_star_order, ZZbig) {
131                Fq.canonical_gen()
132            } else {
133                get_prim_root_of_unity_gen(&Fq, &Fq_star_order, ZZbig, &Fq_star_order).unwrap()
134            };
135            // I thought for a while that it would be enough to have a primitive `lcm(Fq_star_order, large_d^inf)`-th root of unity,
136            // however it is not guaranteed that this would indeed generate the field
137            let FqX = DensePolyRing::new(&Fq, "X");
138            let minpoly = FqX.prod((0..small_d).map(|i| FqX.from_terms([(Fq.negate(Fq.pow_gen(Fq.clone_el(&primitive_element), &ZZbig.pow(ZZbig.clone_el(&p), i as usize), ZZbig)), 0), (Fq.one(), 1)].into_iter())));
139            let minpoly_Fp = poly_ring.from_terms(FqX.terms(&minpoly).map(|(c, i)| {
140                let c_wrt_basis = Fq.wrt_canonical_basis(c);
141                assert!(c_wrt_basis.iter().skip(1).all(|x| Fp.is_zero(&x)));
142                return (c_wrt_basis.at(0), i);
143            }));
144            let f = poly_ring.evaluate(&minpoly_Fp, &poly_ring.from_terms([(Fp.one(), large_d as usize)].into_iter()), &poly_ring.inclusion());
145            return f;
146        }
147    }
148
149    // fallback, just generate a random irreducible polynomial
150    loop {
151        let f = poly_ring.from_terms((0..degree).map(|i| (Fp.random_element(|| rng.rand_u64()), i)).chain([(Fp.one(), degree)].into_iter()));
152        if let Some(result) = filter_irreducible(&poly_ring, create_mod_f_ring(&f), degree) {
153            return result;
154        }
155    }
156}
157
158fn find_small_irreducible_poly<P>(poly_ring: P, degree: usize, rng: &mut oorandom::Rand64) -> El<P>
159    where P: RingStore,
160        P::Type: PolyRing + EuclideanRing,
161        <P::Type as RingExtension>::BaseRing: Copy,
162        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>
163{
164    static_assert_impls!(<<P::Type as RingExtension>::BaseRing as RingStore>::Type: PolyTFracGCDRing);
165    
166    let log2_modulus = poly_ring.base_ring().integer_ring().abs_log2_ceil(poly_ring.base_ring().modulus()).unwrap();
167    let fft_convolution = FFTConvolution::new_with_alloc(Global);
168    if fft_convolution.has_sufficient_precision(StaticRing::<i64>::RING.abs_log2_ceil(&degree.try_into().unwrap()).unwrap() + 1, log2_modulus) {
169        find_small_irreducible_poly_base(
170            &poly_ring,
171            degree,
172            <FFTConvolutionZn as From<_>>::from(fft_convolution),
173            rng
174        )
175    } else {
176        find_small_irreducible_poly_base(
177            &poly_ring,
178            degree,
179            STANDARD_CONVOLUTION,
180            rng
181        )
182    }
183}
184
185///
186/// Implementation of a galois field `GF(p^e)`; Also known as galois field, and sometimes denoted by `Fq` where `q = p^e`. 
187/// 
188/// There exists a finite field with `q` elements if and only if `q = p^e` is a prime power. In these cases,
189/// this struct provides an implementation of arithmetic in these fields. Note that since those fields are always finite-degree
190/// extensions of `Z/pZ`, they can also be used by creating a suitable instance of [`super::extension_impl::FreeAlgebraImpl`]. In fact,
191/// this is the way the old implementation of galois fields was designed. However, providing a new type can provide both 
192/// ergonomic and performance benefits, and also gives better encapsulation.
193/// 
194/// # Example
195/// 
196/// The easiest way to create a Galois field is by using `new()`:
197/// ```rust
198/// # use feanor_math::ring::*;
199/// # use feanor_math::rings::extension::*;
200/// # use feanor_math::rings::finite::*;
201/// # use feanor_math::homomorphism::*;
202/// # use feanor_math::primitive_int::*;
203/// # use feanor_math::rings::extension::galois_field::*;
204/// let F25: GaloisField = GaloisField::new(5, 2);
205/// assert_eq!(5, F25.characteristic(&StaticRing::<i64>::RING).unwrap());
206/// assert_eq!(2, F25.rank());
207/// ```
208/// More configurations are possible using [`GaloisField::new_with_convolution()`] or [`GaloisField::create()`].
209/// 
210/// We also support conversion to and from a plain [`super::extension_impl::FreeAlgebraImpl`] representation.
211/// ```rust
212/// # use feanor_math::ring::*;
213/// # use feanor_math::rings::extension::*;
214/// # use feanor_math::rings::extension::extension_impl::*;
215/// # use feanor_math::rings::field::*;
216/// # use feanor_math::rings::finite::*;
217/// # use feanor_math::homomorphism::*;
218/// # use feanor_math::primitive_int::*;
219/// # use feanor_math::rings::extension::galois_field::*;
220/// let F25: GaloisField = GaloisField::new(5, 2);
221/// let raw_F25: AsField<FreeAlgebraImpl<_, _>> = F25.clone().into().unwrap_self();
222/// assert!(F25.can_iso(&raw_F25).is_some());
223/// ```
224/// The other way is slightly more dangerous, since at some point we either have to check, or assume
225/// that the extension ring is indeed a field.
226/// ```rust
227/// # use feanor_math::ring::*;
228/// # use feanor_math::rings::extension::*;
229/// # use feanor_math::rings::extension::extension_impl::*;
230/// # use feanor_math::rings::field::*;
231/// # use feanor_math::rings::finite::*;
232/// # use feanor_math::homomorphism::*;
233/// # use feanor_math::rings::zn::zn_64::*;
234/// # use feanor_math::rings::zn::*;
235/// # use feanor_math::primitive_int::*;
236/// # use feanor_math::rings::extension::galois_field::*;
237/// let base_ring = Zn::new(5).as_field().ok().unwrap();
238/// let raw_F25: FreeAlgebraImpl<_, _> = FreeAlgebraImpl::new(base_ring, 2, [base_ring.int_hom().map(2)]);
239/// let asfield_F25 = raw_F25.clone().as_field().ok().unwrap();
240/// // alternatively, you can ensure yourself that the ring is a field and use `promise_is_field` to avoid the check at runtime; be careful when doing this!
241/// let asfield_F25 = AsField::from(AsFieldBase::promise_is_field(raw_F25).ok().unwrap());
242/// let F25 = GaloisField::create(asfield_F25);
243/// assert!(F25.can_iso(&raw_F25).is_some());
244/// ```
245/// 
246/// # Choice of blanket implementations of [`CanHomFrom`]
247/// 
248/// As opposed to the more generic [`DelegateRing`]s, here I chose a "ping-pong" way
249/// of implementing [`CanHomFrom`] and [`CanIsoFromTo`] for [`GaloisFieldBase`] that is
250/// very powerful when we use the standard `Impl = AsField<FreeAlgebraImpl<_, _, _, _>>`.
251/// In particular, we implement `GaloisFieldBase<Impl>: CanHomFrom<S>` for all `S` with 
252/// `Impl: CanHomFrom<S>`. It is great that we can provide such a large class of blanket impls,
253/// however this impl will then conflict with (almost) all other impls - which is the reason
254/// why we don't do it e.g. for [`AsFieldBase`].
255/// 
256/// Instead, we complement it with just the impls `FreeAlgebraImplBase<_, _, _, _>: CanHomFrom<GaloisFieldBase<_>>`
257/// and `AsFieldBase<FreeAlgebraImpl<_, _, _, _>>: CanHomFrom<GaloisFieldBase<_>>`. This means
258/// that if `Impl = AsFieldBase<FreeAlgebraImpl<_, _, _, _>>`, together with the blanket implementation,
259/// it gives the very much desired self-isomorphism `GaloisFieldBase<_>: CanHomFrom<GaloisFieldBase<_>>`.
260/// The only downside of this approach is that `GaloisFieldBase` does not have a canonical self-isomorphism
261/// anymore if a nonstandard `Impl` is chosen - which I believe will be very rarely the case in practice.
262/// 
263#[repr(transparent)]
264#[derive(Debug)]
265pub struct GaloisFieldBase<Impl>
266    where Impl: RingStore,
267        Impl::Type: Field + FreeAlgebra + FiniteRing,
268        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
269{
270    base: Impl
271}
272
273///
274/// The default implementation of a finite field extension of a prime field, 
275/// based on [`Zn`].
276/// 
277pub type DefaultGaloisFieldImpl = AsField<FreeAlgebraImpl<AsField<Zn>, SparseMapVector<AsField<Zn>>, Global, KaratsubaAlgorithm>>;
278
279///
280/// Implementation of finite/galois fields.
281/// 
282/// This is the [`RingStore`] corresponding to [`GaloisFieldBase`]. For more details, see [`GaloisFieldBase`].
283/// 
284pub type GaloisField<Impl = DefaultGaloisFieldImpl> = RingValue<GaloisFieldBase<Impl>>;
285
286///
287/// Type alias for the most common instantiation of [`GaloisField`], which
288/// uses [`FreeAlgebraImpl`] to compute ring arithmetic.
289/// 
290pub type GaloisFieldOver<R, A = Global, C = KaratsubaAlgorithm> = RingValue<GaloisFieldBaseOver<R, A, C>>;
291
292///
293/// Type alias for the most common instantiation of [`GaloisFieldBase`], which
294/// uses [`FreeAlgebraImpl`] to compute ring arithmetic.
295/// 
296pub type GaloisFieldBaseOver<R, A = Global, C = KaratsubaAlgorithm> = GaloisFieldBase<AsField<FreeAlgebraImpl<R, SparseMapVector<R>, A, C>>>;
297
298impl GaloisField {
299
300    ///
301    /// Creates a new instance of the finite/galois field `GF(p^degree)`.
302    /// 
303    /// If you need more options for configuration, consider using [`GaloisField::new_with_convolution()`] or
304    /// the most general [`GaloisField::create()`].
305    /// 
306    /// # Example
307    /// ```rust
308    /// # use feanor_math::ring::*;
309    /// # use feanor_math::rings::extension::*;
310    /// # use feanor_math::rings::finite::*;
311    /// # use feanor_math::homomorphism::*;
312    /// # use feanor_math::rings::extension::galois_field::*;
313    /// let F25 = GaloisField::new(5, 2);
314    /// let generator = F25.canonical_gen();
315    /// let norm = F25.mul_ref_fst(&generator, F25.pow(F25.clone_el(&generator), 5));
316    /// let inclusion = F25.inclusion();
317    /// // the norm must be an element of the prime field
318    /// assert!(F25.base_ring().elements().any(|x| {
319    ///     F25.eq_el(&norm, &inclusion.map(x))
320    /// }));
321    /// ```
322    /// 
323    /// # Panics
324    /// 
325    /// Panics if `Z/pZ` is not a field, namely if `p` is not prime.
326    /// 
327    pub fn new(p: i64, degree: usize) -> Self {
328        let field = match Zn::new(p as u64).as_field() {
329            Ok(field) => field,
330            Err(_) => panic!("characteristic {p} is not a prime"),
331        };
332
333        Self::new_with_convolution(field, degree, Global, STANDARD_CONVOLUTION)
334    }
335}
336
337impl<R, A, C> GaloisFieldOver<R, A, C>
338    where R: RingStore + Clone,
339        R::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>,
340        C: ConvolutionAlgorithm<R::Type>,
341        A: Allocator + Clone
342{
343    ///
344    /// Creates a new instance of a finite/galois field, as given-degree extension of the
345    /// given base ring. The base ring must have prime characteristic.
346    /// 
347    /// If you need to specify the minimal polynomial used, see also [`GaloisField::create()`].
348    /// 
349    /// # Example
350    /// 
351    /// Sometimes it is useful to have the base ring also be a field. This can e.g. be achieved
352    /// by
353    /// ```rust
354    /// #![feature(allocator_api)]
355    /// # use std::alloc::Global;
356    /// # use feanor_math::ring::*;
357    /// # use feanor_math::rings::extension::*;
358    /// # use feanor_math::rings::finite::*;
359    /// # use feanor_math::homomorphism::*;
360    /// # use feanor_math::rings::zn::zn_64::*;
361    /// # use feanor_math::rings::zn::*;
362    /// # use feanor_math::algorithms::convolution::*;
363    /// # use feanor_math::rings::extension::galois_field::*;
364    /// let F25 = GaloisField::new_with_convolution(Zn::new(5).as_field().ok().unwrap(), 2, Global, STANDARD_CONVOLUTION);
365    /// let generator = F25.canonical_gen();
366    /// let norm = F25.mul_ref_fst(&generator, F25.pow(F25.clone_el(&generator), 5));
367    /// let inclusion = F25.inclusion();
368    /// // the norm must be an element of the prime field
369    /// assert!(F25.base_ring().elements().any(|x| {
370    ///     F25.eq_el(&norm, &inclusion.map(x))
371    /// }));
372    /// ```
373    /// 
374    #[stability::unstable(feature = "enable")]
375    pub fn new_with_convolution(base_field: R, degree: usize, allocator: A, convolution_algorithm: C) -> Self {
376        assert!(degree >= 1);
377        let poly_ring = DensePolyRing::new(&base_field, "X");
378        let mut rng = oorandom::Rand64::new(poly_ring.base_ring().integer_ring().default_hash(poly_ring.base_ring().modulus()) as u128);
379        let modulus = find_small_irreducible_poly(&poly_ring, degree, &mut rng);
380        let mut modulus_vec = SparseMapVector::new(degree, base_field.clone());
381        for (c, i) in poly_ring.terms(&modulus) {
382            if i != degree {
383                *modulus_vec.at_mut(i) = base_field.negate(base_field.clone_el(c));
384            }
385        }
386        return RingValue::from(GaloisFieldBase { 
387            base: AsField::from(AsFieldBase::promise_is_perfect_field(FreeAlgebraImpl::new_with_convolution(base_field, degree, modulus_vec, "θ", allocator, convolution_algorithm)))
388        });
389    }
390
391    ///
392    /// Instantiates the galois field by calling `find_small_irreducible_poly()` with a poly ring whose base ring
393    /// is exactly `R`; this prevents infinite generic argument recursion, which might otherwise happen if each
394    /// recursive call adds a reference `&` to `R`.
395    /// 
396    fn new_internal(base_ring: R, degree: usize, allocator: A, convolution_algorithm: C) -> Self
397        where R: Copy
398    {
399        assert!(degree >= 1);
400        let poly_ring = DensePolyRing::new(base_ring.clone(), "X");
401        let mut rng = oorandom::Rand64::new(poly_ring.base_ring().integer_ring().default_hash(poly_ring.base_ring().modulus()) as u128);
402        let modulus = find_small_irreducible_poly(&poly_ring, degree, &mut rng);
403        let mut modulus_vec = SparseMapVector::new(degree, base_ring.clone());
404        for (c, i) in poly_ring.terms(&modulus) {
405            if i != degree {
406                *modulus_vec.at_mut(i) = base_ring.negate(base_ring.clone_el(c));
407            }
408        }
409        return RingValue::from(GaloisFieldBase { 
410            base: AsField::from(AsFieldBase::promise_is_perfect_field(FreeAlgebraImpl::new_with_convolution(base_ring, degree, modulus_vec, "θ", allocator, convolution_algorithm)))
411        });
412    }
413}
414
415impl<A> GaloisFieldBase<AsField<FreeAlgebraImpl<AsField<Zn>, SparseMapVector<AsField<Zn>>, A, KaratsubaAlgorithm>>>
416    where A: Allocator + Clone
417{
418    ///
419    /// Creates the galois ring `GR(p, e, degree)`, mirroring the structure of this galois field.
420    /// 
421    /// A galois ring is similar to a galois field, but not a field anymore since it has prime power characteristic
422    /// instead of prime characteristic. It can be constructed as `(Z/p^eZ)[X]/(f)` where `f` is a monic polynomial
423    /// of degree `degree` such that `f mod p` is irreducible. When using this function, the generating polynomial of
424    /// the resulting galois ring will be the coefficient-wise shortest lift of the generating polynomial of this
425    /// galois field.
426    /// 
427    /// For more configuration options, use [`GaloisFieldBase::galois_ring_with()`].
428    /// 
429    #[stability::unstable(feature = "enable")]
430    pub fn galois_ring(&self, e: usize) -> AsLocalPIR<FreeAlgebraImpl<Zn, SparseMapVector<Zn>, A, KaratsubaAlgorithm>> {
431        self.galois_ring_with(Zn::new(StaticRing::<i64>::RING.pow(*self.base_ring().modulus(), e) as u64), self.base.get_ring().get_delegate().allocator().clone(), STANDARD_CONVOLUTION)
432    }
433}
434
435impl<Impl> GaloisFieldBase<Impl>
436    where Impl: RingStore,
437        Impl::Type: Field + FreeAlgebra + FiniteRing,
438        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
439{
440    /// 
441    /// Creates the galois ring `GR(p, e, degree)`, mirroring the structure of this galois field.
442    /// 
443    /// A galois ring is similar to a galois field, but not a field anymore since it has prime power characteristic
444    /// instead of prime characteristic. It can be constructed as `(Z/p^eZ)[X]/(f)` where `f` is a monic polynomial
445    /// of degree `degree` such that `f mod p` is irreducible. When using this function, the generating polynomial of
446    /// the resulting galois ring will be the coefficient-wise shortest lift of the generating polynomial of this
447    /// galois field.
448    /// 
449    /// See also [`GaloisFieldBase::galois_ring()`] for a simpler version of this function.
450    /// 
451    #[stability::unstable(feature = "enable")]
452    pub fn galois_ring_with<S, A2, C2>(&self, new_base_ring: S, allocator: A2, convolution_algorithm: C2) -> AsLocalPIR<FreeAlgebraImpl<S, SparseMapVector<S>, A2, C2>>
453        where S: RingStore + Clone,
454            S::Type: ZnRing + CanHomFrom<<<<Impl::Type as RingExtension>::BaseRing as RingStore>::Type as ZnRing>::IntegerRingBase>,
455            C2: ConvolutionAlgorithm<S::Type>,
456            A2: Allocator + Clone
457    {
458        let (p, e) = is_prime_power(&BigIntRing::RING, &new_base_ring.size(&BigIntRing::RING).unwrap()).unwrap();
459        assert!(BigIntRing::RING.eq_el(&p, &self.base_ring().size(&BigIntRing::RING).unwrap()));
460        let mut modulus_vec = SparseMapVector::new(self.rank(), new_base_ring.clone());
461        let x_pow_deg = RingRef::new(self).pow(self.canonical_gen(), self.rank());
462        let x_pow_deg = self.wrt_canonical_basis(&x_pow_deg);
463        let hom = new_base_ring.can_hom(self.base_ring().integer_ring()).unwrap();
464        for i in 0..self.rank() {
465            if !self.base_ring().is_zero(&x_pow_deg.at(i)) {
466                *modulus_vec.at_mut(i) = hom.map(self.base_ring().smallest_lift(x_pow_deg.at(i)));
467            }
468        }
469        let result = FreeAlgebraImpl::new_with_convolution(
470            new_base_ring,
471            self.rank(),
472            modulus_vec,
473            "θ",
474            allocator,
475            convolution_algorithm
476        );
477        let hom = result.base_ring().can_hom(self.base_ring().integer_ring()).unwrap();
478        let max_ideal_gen = result.inclusion().map(hom.map_ref(self.base_ring().modulus()));
479        return AsLocalPIR::from(AsLocalPIRBase::promise_is_local_pir(result, max_ideal_gen, Some(e)));
480    }
481
482    #[stability::unstable(feature = "enable")]
483    pub fn unwrap_self(self) -> Impl {
484        self.base
485    }
486}
487
488impl<Impl> GaloisField<Impl>
489    where Impl: RingStore,
490        Impl::Type: Field + FreeAlgebra + FiniteRing,
491        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
492{
493    ///
494    /// Most generic function to create a finite/galois field.
495    /// 
496    /// It allows specifying all associated data. Note also that the passed implementation
497    /// must indeed be a field, and this is not checked at runtime. Passing a non-field
498    /// is impossible, unless [`AsFieldBase::promise_is_field()`] is used.
499    /// 
500    #[stability::unstable(feature = "enable")]
501    pub fn create(base: Impl) -> Self {
502        RingValue::from(GaloisFieldBase {
503            base: base
504        })
505    }
506}
507
508impl<Impl> Clone for GaloisFieldBase<Impl>
509    where Impl: RingStore + Clone,
510        Impl::Type: Field + FreeAlgebra + FiniteRing,
511        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
512{
513    fn clone(&self) -> Self {
514        Self {
515            base: self.base.clone()
516        }
517    }
518}
519
520impl<Impl> Copy for GaloisFieldBase<Impl> 
521    where Impl: RingStore + Copy,
522        Impl::Type: Field + FreeAlgebra + FiniteRing,
523        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
524        El<Impl>: Copy
525{}
526
527impl<Impl> PartialEq for GaloisFieldBase<Impl>
528    where Impl: RingStore,
529        Impl::Type: Field + FreeAlgebra + FiniteRing,
530        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
531{
532    fn eq(&self, other: &Self) -> bool {
533        self.base.get_ring() == other.base.get_ring()
534    }
535}
536
537impl<Impl> DelegateRing for GaloisFieldBase<Impl>
538    where Impl: RingStore,
539        Impl::Type: Field + FreeAlgebra + FiniteRing,
540        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
541{
542    type Base = Impl::Type;
543    type Element = El<Impl>;
544
545    fn delegate(&self, el: Self::Element) -> <Self::Base as RingBase>::Element { el }
546    fn delegate_mut<'a>(&self, el: &'a mut Self::Element) -> &'a mut <Self::Base as RingBase>::Element { el }
547    fn delegate_ref<'a>(&self, el: &'a Self::Element) -> &'a <Self::Base as RingBase>::Element { el }
548    fn rev_delegate(&self, el: <Self::Base as RingBase>::Element) -> Self::Element { el }
549
550    fn get_delegate(&self) -> &Self::Base {
551        self.base.get_ring()
552    }
553}
554
555impl<Impl> DelegateRingImplFiniteRing for GaloisFieldBase<Impl>
556    where Impl: RingStore,
557        Impl::Type: Field + FreeAlgebra + FiniteRing,
558        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
559{}
560
561impl<Impl> Domain for GaloisFieldBase<Impl>
562    where Impl: RingStore,
563        Impl::Type: Field + FreeAlgebra + FiniteRing,
564        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
565{}
566
567impl<Impl> Field for GaloisFieldBase<Impl>
568    where Impl: RingStore,
569        Impl::Type: Field + FreeAlgebra + FiniteRing,
570        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
571{}
572
573impl<Impl> PerfectField for GaloisFieldBase<Impl>
574    where Impl: RingStore,
575        Impl::Type: Field + FreeAlgebra + FiniteRing,
576        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
577{}
578
579// impl<Impl> LinSolveRing for GaloisFieldBase<Impl>
580//     where Impl: RingStore,
581//         Impl::Type: Field + FreeAlgebra + FiniteRing,
582//         <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
583// {
584//     fn solve_right<V1, V2, V3, A>(&self, lhs: crate::matrix::SubmatrixMut<V1, Self::Element>, rhs: crate::matrix::SubmatrixMut<V2, Self::Element>, out: crate::matrix::SubmatrixMut<V3, Self::Element>, allocator: A) -> crate::algorithms::linsolve::SolveResult
585//         where V1: crate::matrix::AsPointerToSlice<Self::Element>,
586//             V2: crate::matrix::AsPointerToSlice<Self::Element>,
587//             V3: crate::matrix::AsPointerToSlice<Self::Element>,
588//             A: Allocator
589//     {
590//         unimplemented!()
591//     }
592// }
593
594impl<Impl> EuclideanRing for GaloisFieldBase<Impl>
595    where Impl: RingStore,
596        Impl::Type: Field + FreeAlgebra + FiniteRing,
597        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
598{
599    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
600        assert!(!self.is_zero(rhs));
601        (self.base.checked_div(&lhs, rhs).unwrap(), self.zero())
602    }
603
604    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
605        if self.is_zero(val) {
606            Some(0)
607        } else {
608            Some(1)
609        }
610    }
611
612    fn euclidean_rem(&self, _: Self::Element, rhs: &Self::Element) -> Self::Element {
613        assert!(!self.is_zero(rhs));
614        self.zero()
615    }
616}
617
618impl<Impl> PrincipalIdealRing for GaloisFieldBase<Impl>
619    where Impl: RingStore,
620        Impl::Type: Field + FreeAlgebra + FiniteRing,
621        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
622{
623    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
624        if self.is_zero(lhs) && self.is_zero(rhs) {
625            Some(self.one())
626        } else {
627            self.checked_left_div(lhs, rhs)
628        }
629    }
630    
631    fn extended_ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element, Self::Element) {
632        if self.is_zero(lhs) {
633            (self.zero(), self.one(), self.clone_el(rhs))
634        } else {
635            (self.one(), self.zero(), self.clone_el(lhs))
636        }
637    }
638}
639
640impl<Impl> Serialize for GaloisFieldBase<Impl>
641    where Impl: RingStore + Serialize,
642        Impl::Type: Field + FreeAlgebra + FiniteRing + SerializableElementRing,
643        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
644{
645    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
646        where S: Serializer
647    {
648        SerializableNewtypeStruct::new("GaloisField", &self.base).serialize(serializer)
649    }
650}
651
652impl<'de, Impl> Deserialize<'de> for GaloisFieldBase<Impl>
653    where Impl: RingStore + Deserialize<'de>,
654        Impl::Type: Field + FreeAlgebra + FiniteRing + SerializableElementRing,
655        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
656{
657    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
658        where D: Deserializer<'de>
659    {
660        DeserializeSeedNewtypeStruct::new("GaloisField", PhantomData::<Impl>).deserialize(deserializer).map(|res| GaloisField::create(res).into())
661    }
662}
663
664impl<Impl> KaratsubaHint for GaloisFieldBase<Impl>
665    where Impl: RingStore,
666        Impl::Type: Field + FreeAlgebra + FiniteRing,
667        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
668{
669    fn karatsuba_threshold(&self) -> usize {
670        self.get_delegate().karatsuba_threshold()
671    }
672}
673
674impl<Impl> ComputeInnerProduct for GaloisFieldBase<Impl>
675    where Impl: RingStore,
676        Impl::Type: Field + FreeAlgebra + FiniteRing,
677        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
678{
679    fn inner_product<I: Iterator<Item = (Self::Element, Self::Element)>>(&self, els: I) -> Self::Element {
680        self.rev_delegate(self.get_delegate().inner_product(els.map(|(a, b)| (self.delegate(a), self.delegate(b)))))
681    }
682
683    fn inner_product_ref<'a, I: Iterator<Item = (&'a Self::Element, &'a Self::Element)>>(&self, els: I) -> Self::Element
684        where Self::Element: 'a,
685            Self: 'a
686    {
687        self.rev_delegate(self.get_delegate().inner_product_ref(els.map(|(a, b)| (self.delegate_ref(a), self.delegate_ref(b)))))
688    }
689
690    fn inner_product_ref_fst<'a, I: Iterator<Item = (&'a Self::Element, Self::Element)>>(&self, els: I) -> Self::Element
691        where Self::Element: 'a,
692            Self: 'a
693    {
694        self.rev_delegate(self.get_delegate().inner_product_ref_fst(els.map(|(a, b)| (self.delegate_ref(a), self.delegate(b)))))
695    }
696}
697
698impl<Impl> StrassenHint for GaloisFieldBase<Impl>
699    where Impl: RingStore,
700        Impl::Type: Field + FreeAlgebra + FiniteRing,
701        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
702{
703    fn strassen_threshold(&self) -> usize {
704        self.get_delegate().strassen_threshold()
705    }
706}
707
708///
709/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
710/// 
711impl<Impl, S> CanHomFrom<S> for GaloisFieldBase<Impl>
712    where Impl: RingStore,
713        Impl::Type: Field + FreeAlgebra + FiniteRing + CanHomFrom<S>,
714        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
715        S: ?Sized + RingBase
716{
717    type Homomorphism = <Impl::Type as CanHomFrom<S>>::Homomorphism;
718
719    fn has_canonical_hom(&self, from: &S) -> Option<Self::Homomorphism> {
720        self.base.get_ring().has_canonical_hom(from)
721    }
722
723    fn map_in(&self, from: &S, el: <S as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
724        self.base.get_ring().map_in(from, el, hom)
725    }
726}
727
728///
729/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
730/// 
731impl<Impl, R, A, V, C> CanHomFrom<GaloisFieldBase<Impl>> for FreeAlgebraImplBase<R, V, A, C>
732    where Impl: RingStore,
733        Impl::Type: Field + FreeAlgebra + FiniteRing,
734        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
735        R: RingStore,
736        V: VectorView<El<R>>,
737        C: ConvolutionAlgorithm<R::Type>,
738        A: Allocator + Clone,
739        FreeAlgebraImplBase<R, V, A, C>: CanHomFrom<Impl::Type>
740{
741    type Homomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanHomFrom<Impl::Type>>::Homomorphism;
742
743    fn has_canonical_hom(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Homomorphism> {
744        self.has_canonical_hom(from.base.get_ring())
745    }
746
747    fn map_in(&self, from: &GaloisFieldBase<Impl>, el: <GaloisFieldBase<Impl> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
748        self.map_in(from.base.get_ring(), el, hom)
749    }
750}
751
752///
753/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
754/// 
755impl<Impl, R, A, V, C> CanHomFrom<GaloisFieldBase<Impl>> for AsFieldBase<FreeAlgebraImpl<R, V, A, C>>
756    where Impl: RingStore,
757        Impl::Type: Field + FreeAlgebra + FiniteRing,
758        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
759        R: RingStore,
760        R::Type: LinSolveRing,
761        V: VectorView<El<R>>,
762        C: ConvolutionAlgorithm<R::Type>,
763        A: Allocator + Clone,
764        FreeAlgebraImplBase<R, V, A, C>: CanHomFrom<Impl::Type>
765{
766    type Homomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanHomFrom<Impl::Type>>::Homomorphism;
767
768    fn has_canonical_hom(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Homomorphism> {
769        self.get_delegate().has_canonical_hom(from.base.get_ring())
770    }
771
772    fn map_in(&self, from: &GaloisFieldBase<Impl>, el: <GaloisFieldBase<Impl> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
773        self.rev_delegate(self.get_delegate().map_in(from.base.get_ring(), el, hom))
774    }
775}
776
777///
778/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
779/// 
780impl<Impl, S> CanIsoFromTo<S> for GaloisFieldBase<Impl>
781    where Impl: RingStore,
782        Impl::Type: Field + FreeAlgebra + FiniteRing + CanIsoFromTo<S>,
783        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
784        S: ?Sized + RingBase
785{
786    type Isomorphism = <Impl::Type as CanIsoFromTo<S>>::Isomorphism;
787
788    fn has_canonical_iso(&self, from: &S) -> Option<Self::Isomorphism> {
789        self.base.get_ring().has_canonical_iso(from)
790    }
791
792    fn map_out(&self, from: &S, el: Self::Element, iso: &Self::Isomorphism) -> <S as RingBase>::Element {
793        self.base.get_ring().map_out(from, el, iso)
794    }
795}
796
797///
798/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
799/// 
800impl<Impl, R, A, V, C> CanIsoFromTo<GaloisFieldBase<Impl>> for FreeAlgebraImplBase<R, V, A, C>
801    where Impl: RingStore,
802        Impl::Type: Field + FreeAlgebra + FiniteRing,
803        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
804        R: RingStore,
805        V: VectorView<El<R>>,
806        C: ConvolutionAlgorithm<R::Type>,
807        A: Allocator + Clone,
808        FreeAlgebraImplBase<R, V, A, C>: CanIsoFromTo<Impl::Type>
809{
810    type Isomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanIsoFromTo<Impl::Type>>::Isomorphism;
811
812    fn has_canonical_iso(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Isomorphism> {
813        self.has_canonical_iso(from.base.get_ring())
814    }
815    
816    fn map_out(&self, from: &GaloisFieldBase<Impl>, el: Self::Element, iso: &Self::Isomorphism) -> <GaloisFieldBase<Impl> as RingBase>::Element {
817        self.map_out(from.base.get_ring(), el, iso)
818    }
819}
820
821///
822/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
823/// 
824impl<Impl, R, A, V, C> CanIsoFromTo<GaloisFieldBase<Impl>> for AsFieldBase<FreeAlgebraImpl<R, V, A, C>>
825    where Impl: RingStore,
826        Impl::Type: Field + FreeAlgebra + FiniteRing,
827        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
828        R: RingStore,
829        R::Type: LinSolveRing,
830        V: VectorView<El<R>>,
831        C: ConvolutionAlgorithm<R::Type>,
832        A: Allocator + Clone,
833        FreeAlgebraImplBase<R, V, A, C>: CanIsoFromTo<Impl::Type>
834{
835    type Isomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanIsoFromTo<Impl::Type>>::Isomorphism;
836
837    fn has_canonical_iso(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Isomorphism> {
838        self.get_delegate().has_canonical_iso(from.base.get_ring())
839    }
840    
841    fn map_out(&self, from: &GaloisFieldBase<Impl>, el: Self::Element, iso: &Self::Isomorphism) -> <GaloisFieldBase<Impl> as RingBase>::Element {
842        self.get_delegate().map_out(from.base.get_ring(), self.delegate(el), iso)
843    }
844}
845
846#[cfg(test)]
847use test::Bencher;
848#[cfg(test)]
849use std::time::Instant;
850
851#[test]
852fn test_can_hom_from() {
853    #[allow(unused)]
854    fn assert_impl_CanHomFrom<From, To>()
855        where To: ?Sized + CanHomFrom<From>, From: ?Sized + RingBase 
856    {}
857    
858    #[allow(unused)]
859    fn FreeAlgebraImpl_wrap_unwrap_homs<R, V, A, C>()
860        where R: RingStore,
861            R::Type: SelfIso + LinSolveRing,
862            V: VectorView<El<R>>,
863            A: Allocator + Clone,
864            C: ConvolutionAlgorithm<R::Type>
865    {
866        assert_impl_CanHomFrom::<FreeAlgebraImplBase<R, V, A, C>, AsFieldBase<FreeAlgebraImpl<R, V, A, C>>>();
867    }
868
869    #[allow(unused)]
870    fn FreeAlgebraImpl_from_GaloisField<R, V, A, C>()
871        where R: RingStore,
872            R::Type: SelfIso + LinSolveRing + FiniteRing + Field + ZnRing,
873            V: VectorView<El<R>>,
874            A: Allocator + Clone,
875            C: ConvolutionAlgorithm<R::Type>
876    {
877        assert_impl_CanHomFrom::<GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>, AsFieldBase<FreeAlgebraImpl<R, V, A, C>>>();
878    }
879
880    #[allow(unused)]
881    fn GaloisField_from_GaloisField<R, V, A, C>()
882        where R: RingStore,
883            R::Type: SelfIso + LinSolveRing + FiniteRing + Field + ZnRing,
884            V: VectorView<El<R>>,
885            A: Allocator + Clone,
886            C: ConvolutionAlgorithm<R::Type>
887    {
888        assert_impl_CanHomFrom::<GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>, GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>>();
889    }
890}
891
892#[test]
893fn test_galois_field() {
894    let field = GaloisField::new(3, 1);
895    assert_eq!(3, field.elements().count());
896    crate::ring::generic_tests::test_ring_axioms(&field, field.elements());
897    crate::ring::generic_tests::test_self_iso(&field, field.elements());
898    crate::field::generic_tests::test_field_axioms(&field, field.elements());
899
900    let field = GaloisField::new(3, 2);
901    assert_eq!(9, field.elements().count());
902    crate::ring::generic_tests::test_ring_axioms(&field, field.elements());
903    crate::ring::generic_tests::test_self_iso(&field, field.elements());
904    crate::field::generic_tests::test_field_axioms(&field, field.elements());
905}
906
907#[test]
908fn test_principal_ideal_ring_axioms() {
909    let field = GaloisField::new(3, 2);
910    crate::pid::generic_tests::test_principal_ideal_ring_axioms(&field, field.elements());
911    crate::pid::generic_tests::test_euclidean_ring_axioms(&field, field.elements());
912}
913
914#[test]
915fn test_galois_field_even() {
916    for degree in 1..=9 {
917        let field = GaloisField::new_with_convolution(Zn::new(2).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
918        assert_eq!(degree, field.rank());
919        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
920    }
921}
922
923#[test]
924fn test_galois_field_odd() {
925    for degree in 1..=9 {
926        let field = GaloisField::new_with_convolution(Zn::new(3).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
927        assert_eq!(degree, field.rank());
928        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
929    }
930
931    for degree in 1..=9 {
932        let field = GaloisField::new_with_convolution(Zn::new(5).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
933        assert_eq!(degree, field.rank());
934        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
935    }
936}
937
938#[test]
939fn test_galois_field_no_trinomial() {
940    let field = GaloisField::new_with_convolution(Zn::new(2).as_field().ok().unwrap(), 24, Global, STANDARD_CONVOLUTION);
941    assert_eq!(24, field.rank());
942    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
943    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
944    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
945
946    let field = GaloisField::new_with_convolution(Zn::new(3).as_field().ok().unwrap(), 30, Global, STANDARD_CONVOLUTION);
947    assert_eq!(30, field.rank());
948    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
949    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
950    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
951
952    let field = GaloisField::new_with_convolution(Zn::new(17).as_field().ok().unwrap(), 32, Global, STANDARD_CONVOLUTION);
953    assert_eq!(32, field.rank());
954    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
955    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
956    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
957}
958
959#[bench]
960fn bench_create_galois_ring_2_14_96(bencher: &mut Bencher) {
961    bencher.iter(|| {
962        let field = GaloisField::new(2, 96);
963        let ring = field.get_ring().galois_ring(14);
964        assert_eq!(96, ring.rank());
965    });
966}
967
968#[test]
969#[ignore]
970fn test_galois_field_huge() {
971    let start = Instant::now();
972    let field = GaloisField::new(17, 2048);
973    _ = std::hint::black_box(field);
974    let end = Instant::now();
975    println!("Created GF(17^2048) in {} ms", (end - start).as_millis());
976}
feanor_math/rings/extension/galois_field.rs

feanor_math/rings/extension/
galois_field.rs
