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

feanor_math/rings/extension/
galois_field.rs
