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).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    pub fn new(p: i64, degree: usize) -> Self {
324        Self::new_with_convolution(Zn::new(p as u64).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION)
325    }
326}
327
328impl<R, A, C> GaloisFieldOver<R, A, C>
329    where R: RingStore + Clone,
330        R::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>,
331        C: ConvolutionAlgorithm<R::Type>,
332        A: Allocator + Clone
333{
334    ///
335    /// Creates a new instance of a finite/galois field, as given-degree extension of the
336    /// given base ring. The base ring must have prime characteristic.
337    /// 
338    /// If you need to specify the minimal polynomial used, see also [`GaloisField::create()`].
339    /// 
340    /// # Example
341    /// 
342    /// Sometimes it is useful to have the base ring also be a field. This can e.g. be achieved
343    /// by
344    /// ```rust
345    /// #![feature(allocator_api)]
346    /// # use std::alloc::Global;
347    /// # use feanor_math::ring::*;
348    /// # use feanor_math::rings::extension::*;
349    /// # use feanor_math::rings::finite::*;
350    /// # use feanor_math::homomorphism::*;
351    /// # use feanor_math::rings::zn::zn_64::*;
352    /// # use feanor_math::rings::zn::*;
353    /// # use feanor_math::algorithms::convolution::*;
354    /// # use feanor_math::rings::extension::galois_field::*;
355    /// let F25 = GaloisField::new_with_convolution(Zn::new(5).as_field().ok().unwrap(), 2, Global, STANDARD_CONVOLUTION);
356    /// let generator = F25.canonical_gen();
357    /// let norm = F25.mul_ref_fst(&generator, F25.pow(F25.clone_el(&generator), 5));
358    /// let inclusion = F25.inclusion();
359    /// // the norm must be an element of the prime field
360    /// assert!(F25.base_ring().elements().any(|x| {
361    ///     F25.eq_el(&norm, &inclusion.map(x))
362    /// }));
363    /// ```
364    /// 
365    #[stability::unstable(feature = "enable")]
366    pub fn new_with_convolution(base_field: R, degree: usize, allocator: A, convolution_algorithm: C) -> Self {
367        assert!(degree >= 1);
368        let poly_ring = DensePolyRing::new(&base_field, "X");
369        let mut rng = oorandom::Rand64::new(poly_ring.base_ring().integer_ring().default_hash(poly_ring.base_ring().modulus()) as u128);
370        let modulus = find_small_irreducible_poly(&poly_ring, degree, &mut rng);
371        let mut modulus_vec = SparseMapVector::new(degree, base_field.clone());
372        for (c, i) in poly_ring.terms(&modulus) {
373            if i != degree {
374                *modulus_vec.at_mut(i) = base_field.negate(base_field.clone_el(c));
375            }
376        }
377        return RingValue::from(GaloisFieldBase { 
378            base: AsField::from(AsFieldBase::promise_is_perfect_field(FreeAlgebraImpl::new_with_convolution(base_field, degree, modulus_vec, "θ", allocator, convolution_algorithm)))
379        });
380    }
381
382    ///
383    /// Instantiates the galois field by calling `find_small_irreducible_poly()` with a poly ring whose base ring
384    /// is exactly `R`; this prevents infinite generic argument recursion, which might otherwise happen if each
385    /// recursive call adds a reference `&` to `R`.
386    /// 
387    fn new_internal(base_ring: R, degree: usize, allocator: A, convolution_algorithm: C) -> Self
388        where R: Copy
389    {
390        assert!(degree >= 1);
391        let poly_ring = DensePolyRing::new(base_ring.clone(), "X");
392        let mut rng = oorandom::Rand64::new(poly_ring.base_ring().integer_ring().default_hash(poly_ring.base_ring().modulus()) as u128);
393        let modulus = find_small_irreducible_poly(&poly_ring, degree, &mut rng);
394        let mut modulus_vec = SparseMapVector::new(degree, base_ring.clone());
395        for (c, i) in poly_ring.terms(&modulus) {
396            if i != degree {
397                *modulus_vec.at_mut(i) = base_ring.negate(base_ring.clone_el(c));
398            }
399        }
400        return RingValue::from(GaloisFieldBase { 
401            base: AsField::from(AsFieldBase::promise_is_perfect_field(FreeAlgebraImpl::new_with_convolution(base_ring, degree, modulus_vec, "θ", allocator, convolution_algorithm)))
402        });
403    }
404}
405
406impl<A> GaloisFieldBase<AsField<FreeAlgebraImpl<AsField<Zn>, SparseMapVector<AsField<Zn>>, A, KaratsubaAlgorithm>>>
407    where A: Allocator + Clone
408{
409    ///
410    /// Creates the galois ring `GR(p, e, degree)`, mirroring the structure of this galois field.
411    /// 
412    /// A galois ring is similar to a galois field, but not a field anymore since it has prime power characteristic
413    /// instead of prime characteristic. It can be constructed as `(Z/p^eZ)[X]/(f)` where `f` is a monic polynomial
414    /// of degree `degree` such that `f mod p` is irreducible. When using this function, the generating polynomial of
415    /// the resulting galois ring will be the coefficient-wise shortest lift of the generating polynomial of this
416    /// galois field.
417    /// 
418    /// For more configuration options, use [`GaloisFieldBase::galois_ring_with()`].
419    /// 
420    #[stability::unstable(feature = "enable")]
421    pub fn galois_ring(&self, e: usize) -> AsLocalPIR<FreeAlgebraImpl<Zn, SparseMapVector<Zn>, A, KaratsubaAlgorithm>> {
422        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)
423    }
424}
425
426impl<Impl> GaloisFieldBase<Impl>
427    where Impl: RingStore,
428        Impl::Type: Field + FreeAlgebra + FiniteRing,
429        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
430{
431    /// 
432    /// Creates the galois ring `GR(p, e, degree)`, mirroring the structure of this galois field.
433    /// 
434    /// A galois ring is similar to a galois field, but not a field anymore since it has prime power characteristic
435    /// instead of prime characteristic. It can be constructed as `(Z/p^eZ)[X]/(f)` where `f` is a monic polynomial
436    /// of degree `degree` such that `f mod p` is irreducible. When using this function, the generating polynomial of
437    /// the resulting galois ring will be the coefficient-wise shortest lift of the generating polynomial of this
438    /// galois field.
439    /// 
440    /// See also [`GaloisFieldBase::galois_ring()`] for a simpler version of this function.
441    /// 
442    #[stability::unstable(feature = "enable")]
443    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>>
444        where S: RingStore + Clone,
445            S::Type: ZnRing + CanHomFrom<<<<Impl::Type as RingExtension>::BaseRing as RingStore>::Type as ZnRing>::IntegerRingBase>,
446            C2: ConvolutionAlgorithm<S::Type>,
447            A2: Allocator + Clone
448    {
449        let (p, e) = is_prime_power(&BigIntRing::RING, &new_base_ring.size(&BigIntRing::RING).unwrap()).unwrap();
450        assert!(BigIntRing::RING.eq_el(&p, &self.base_ring().size(&BigIntRing::RING).unwrap()));
451        let mut modulus_vec = SparseMapVector::new(self.rank(), new_base_ring.clone());
452        let x_pow_deg = RingRef::new(self).pow(self.canonical_gen(), self.rank());
453        let x_pow_deg = self.wrt_canonical_basis(&x_pow_deg);
454        let hom = new_base_ring.can_hom(self.base_ring().integer_ring()).unwrap();
455        for i in 0..self.rank() {
456            if !self.base_ring().is_zero(&x_pow_deg.at(i)) {
457                *modulus_vec.at_mut(i) = hom.map(self.base_ring().smallest_lift(x_pow_deg.at(i)));
458            }
459        }
460        let result = FreeAlgebraImpl::new_with_convolution(
461            new_base_ring,
462            self.rank(),
463            modulus_vec,
464            "θ",
465            allocator,
466            convolution_algorithm
467        );
468        let hom = result.base_ring().can_hom(self.base_ring().integer_ring()).unwrap();
469        let max_ideal_gen = result.inclusion().map(hom.map_ref(self.base_ring().modulus()));
470        return AsLocalPIR::from(AsLocalPIRBase::promise_is_local_pir(result, max_ideal_gen, Some(e)));
471    }
472
473    #[stability::unstable(feature = "enable")]
474    pub fn unwrap_self(self) -> Impl {
475        self.base
476    }
477}
478
479impl<Impl> GaloisField<Impl>
480    where Impl: RingStore,
481        Impl::Type: Field + FreeAlgebra + FiniteRing,
482        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
483{
484    ///
485    /// Most generic function to create a finite/galois field.
486    /// 
487    /// It allows specifying all associated data. Note also that the passed implementation
488    /// must indeed be a field, and this is not checked at runtime. Passing a non-field
489    /// is impossible, unless [`AsFieldBase::promise_is_field()`] is used.
490    /// 
491    #[stability::unstable(feature = "enable")]
492    pub fn create(base: Impl) -> Self {
493        RingValue::from(GaloisFieldBase {
494            base: base
495        })
496    }
497}
498
499impl<Impl> Clone for GaloisFieldBase<Impl>
500    where Impl: RingStore + Clone,
501        Impl::Type: Field + FreeAlgebra + FiniteRing,
502        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
503{
504    fn clone(&self) -> Self {
505        Self {
506            base: self.base.clone()
507        }
508    }
509}
510
511impl<Impl> Copy for GaloisFieldBase<Impl> 
512    where Impl: RingStore + Copy,
513        Impl::Type: Field + FreeAlgebra + FiniteRing,
514        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
515        El<Impl>: Copy
516{}
517
518impl<Impl> PartialEq for GaloisFieldBase<Impl>
519    where Impl: RingStore,
520        Impl::Type: Field + FreeAlgebra + FiniteRing,
521        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
522{
523    fn eq(&self, other: &Self) -> bool {
524        self.base.get_ring() == other.base.get_ring()
525    }
526}
527
528impl<Impl> DelegateRing for GaloisFieldBase<Impl>
529    where Impl: RingStore,
530        Impl::Type: Field + FreeAlgebra + FiniteRing,
531        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
532{
533    type Base = Impl::Type;
534    type Element = El<Impl>;
535
536    fn delegate(&self, el: Self::Element) -> <Self::Base as RingBase>::Element { el }
537    fn delegate_mut<'a>(&self, el: &'a mut Self::Element) -> &'a mut <Self::Base as RingBase>::Element { el }
538    fn delegate_ref<'a>(&self, el: &'a Self::Element) -> &'a <Self::Base as RingBase>::Element { el }
539    fn rev_delegate(&self, el: <Self::Base as RingBase>::Element) -> Self::Element { el }
540
541    fn get_delegate(&self) -> &Self::Base {
542        self.base.get_ring()
543    }
544}
545
546impl<Impl> DelegateRingImplFiniteRing for GaloisFieldBase<Impl>
547    where Impl: RingStore,
548        Impl::Type: Field + FreeAlgebra + FiniteRing,
549        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
550{}
551
552impl<Impl> Domain for GaloisFieldBase<Impl>
553    where Impl: RingStore,
554        Impl::Type: Field + FreeAlgebra + FiniteRing,
555        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
556{}
557
558impl<Impl> Field for GaloisFieldBase<Impl>
559    where Impl: RingStore,
560        Impl::Type: Field + FreeAlgebra + FiniteRing,
561        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
562{}
563
564impl<Impl> PerfectField for GaloisFieldBase<Impl>
565    where Impl: RingStore,
566        Impl::Type: Field + FreeAlgebra + FiniteRing,
567        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
568{}
569
570// impl<Impl> LinSolveRing for GaloisFieldBase<Impl>
571//     where Impl: RingStore,
572//         Impl::Type: Field + FreeAlgebra + FiniteRing,
573//         <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
574// {
575//     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
576//         where V1: crate::matrix::AsPointerToSlice<Self::Element>,
577//             V2: crate::matrix::AsPointerToSlice<Self::Element>,
578//             V3: crate::matrix::AsPointerToSlice<Self::Element>,
579//             A: Allocator
580//     {
581//         unimplemented!()
582//     }
583// }
584
585impl<Impl> EuclideanRing for GaloisFieldBase<Impl>
586    where Impl: RingStore,
587        Impl::Type: Field + FreeAlgebra + FiniteRing,
588        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
589{
590    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
591        assert!(!self.is_zero(rhs));
592        (self.base.checked_div(&lhs, rhs).unwrap(), self.zero())
593    }
594
595    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
596        if self.is_zero(val) {
597            Some(0)
598        } else {
599            Some(1)
600        }
601    }
602
603    fn euclidean_rem(&self, _: Self::Element, rhs: &Self::Element) -> Self::Element {
604        assert!(!self.is_zero(rhs));
605        self.zero()
606    }
607}
608
609impl<Impl> PrincipalIdealRing for GaloisFieldBase<Impl>
610    where Impl: RingStore,
611        Impl::Type: Field + FreeAlgebra + FiniteRing,
612        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
613{
614    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
615        if self.is_zero(lhs) && self.is_zero(rhs) {
616            Some(self.one())
617        } else {
618            self.checked_left_div(lhs, rhs)
619        }
620    }
621    
622    fn extended_ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element, Self::Element) {
623        if self.is_zero(lhs) {
624            (self.zero(), self.one(), self.clone_el(rhs))
625        } else {
626            (self.one(), self.zero(), self.clone_el(lhs))
627        }
628    }
629}
630
631impl<Impl> Serialize for GaloisFieldBase<Impl>
632    where Impl: RingStore + Serialize,
633        Impl::Type: Field + FreeAlgebra + FiniteRing + SerializableElementRing,
634        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
635{
636    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
637        where S: Serializer
638    {
639        SerializableNewtypeStruct::new("GaloisField", &self.base).serialize(serializer)
640    }
641}
642
643impl<'de, Impl> Deserialize<'de> for GaloisFieldBase<Impl>
644    where Impl: RingStore + Deserialize<'de>,
645        Impl::Type: Field + FreeAlgebra + FiniteRing + SerializableElementRing,
646        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
647{
648    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
649        where D: Deserializer<'de>
650    {
651        DeserializeSeedNewtypeStruct::new("GaloisField", PhantomData::<Impl>).deserialize(deserializer).map(|res| GaloisField::create(res).into())
652    }
653}
654
655impl<Impl> KaratsubaHint for GaloisFieldBase<Impl>
656    where Impl: RingStore,
657        Impl::Type: Field + FreeAlgebra + FiniteRing,
658        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
659{
660    fn karatsuba_threshold(&self) -> usize {
661        self.get_delegate().karatsuba_threshold()
662    }
663}
664
665impl<Impl> ComputeInnerProduct for GaloisFieldBase<Impl>
666    where Impl: RingStore,
667        Impl::Type: Field + FreeAlgebra + FiniteRing,
668        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
669{
670    fn inner_product<I: Iterator<Item = (Self::Element, Self::Element)>>(&self, els: I) -> Self::Element {
671        self.rev_delegate(self.get_delegate().inner_product(els.map(|(a, b)| (self.delegate(a), self.delegate(b)))))
672    }
673
674    fn inner_product_ref<'a, I: Iterator<Item = (&'a Self::Element, &'a Self::Element)>>(&self, els: I) -> Self::Element
675        where Self::Element: 'a,
676            Self: 'a
677    {
678        self.rev_delegate(self.get_delegate().inner_product_ref(els.map(|(a, b)| (self.delegate_ref(a), self.delegate_ref(b)))))
679    }
680
681    fn inner_product_ref_fst<'a, I: Iterator<Item = (&'a Self::Element, Self::Element)>>(&self, els: I) -> Self::Element
682        where Self::Element: 'a,
683            Self: 'a
684    {
685        self.rev_delegate(self.get_delegate().inner_product_ref_fst(els.map(|(a, b)| (self.delegate_ref(a), self.delegate(b)))))
686    }
687}
688
689impl<Impl> StrassenHint for GaloisFieldBase<Impl>
690    where Impl: RingStore,
691        Impl::Type: Field + FreeAlgebra + FiniteRing,
692        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
693{
694    fn strassen_threshold(&self) -> usize {
695        self.get_delegate().strassen_threshold()
696    }
697}
698
699///
700/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
701/// 
702impl<Impl, S> CanHomFrom<S> for GaloisFieldBase<Impl>
703    where Impl: RingStore,
704        Impl::Type: Field + FreeAlgebra + FiniteRing + CanHomFrom<S>,
705        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
706        S: ?Sized + RingBase
707{
708    type Homomorphism = <Impl::Type as CanHomFrom<S>>::Homomorphism;
709
710    fn has_canonical_hom(&self, from: &S) -> Option<Self::Homomorphism> {
711        self.base.get_ring().has_canonical_hom(from)
712    }
713
714    fn map_in(&self, from: &S, el: <S as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
715        self.base.get_ring().map_in(from, el, hom)
716    }
717}
718
719///
720/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
721/// 
722impl<Impl, R, A, V, C> CanHomFrom<GaloisFieldBase<Impl>> for FreeAlgebraImplBase<R, V, A, C>
723    where Impl: RingStore,
724        Impl::Type: Field + FreeAlgebra + FiniteRing,
725        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
726        R: RingStore,
727        V: VectorView<El<R>>,
728        C: ConvolutionAlgorithm<R::Type>,
729        A: Allocator + Clone,
730        FreeAlgebraImplBase<R, V, A, C>: CanHomFrom<Impl::Type>
731{
732    type Homomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanHomFrom<Impl::Type>>::Homomorphism;
733
734    fn has_canonical_hom(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Homomorphism> {
735        self.has_canonical_hom(from.base.get_ring())
736    }
737
738    fn map_in(&self, from: &GaloisFieldBase<Impl>, el: <GaloisFieldBase<Impl> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
739        self.map_in(from.base.get_ring(), el, hom)
740    }
741}
742
743///
744/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
745/// 
746impl<Impl, R, A, V, C> CanHomFrom<GaloisFieldBase<Impl>> for AsFieldBase<FreeAlgebraImpl<R, V, A, C>>
747    where Impl: RingStore,
748        Impl::Type: Field + FreeAlgebra + FiniteRing,
749        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
750        R: RingStore,
751        R::Type: LinSolveRing,
752        V: VectorView<El<R>>,
753        C: ConvolutionAlgorithm<R::Type>,
754        A: Allocator + Clone,
755        FreeAlgebraImplBase<R, V, A, C>: CanHomFrom<Impl::Type>
756{
757    type Homomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanHomFrom<Impl::Type>>::Homomorphism;
758
759    fn has_canonical_hom(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Homomorphism> {
760        self.get_delegate().has_canonical_hom(from.base.get_ring())
761    }
762
763    fn map_in(&self, from: &GaloisFieldBase<Impl>, el: <GaloisFieldBase<Impl> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
764        self.rev_delegate(self.get_delegate().map_in(from.base.get_ring(), el, hom))
765    }
766}
767
768///
769/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
770/// 
771impl<Impl, S> CanIsoFromTo<S> for GaloisFieldBase<Impl>
772    where Impl: RingStore,
773        Impl::Type: Field + FreeAlgebra + FiniteRing + CanIsoFromTo<S>,
774        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
775        S: ?Sized + RingBase
776{
777    type Isomorphism = <Impl::Type as CanIsoFromTo<S>>::Isomorphism;
778
779    fn has_canonical_iso(&self, from: &S) -> Option<Self::Isomorphism> {
780        self.base.get_ring().has_canonical_iso(from)
781    }
782
783    fn map_out(&self, from: &S, el: Self::Element, iso: &Self::Isomorphism) -> <S as RingBase>::Element {
784        self.base.get_ring().map_out(from, el, iso)
785    }
786}
787
788///
789/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
790/// 
791impl<Impl, R, A, V, C> CanIsoFromTo<GaloisFieldBase<Impl>> for FreeAlgebraImplBase<R, V, A, C>
792    where Impl: RingStore,
793        Impl::Type: Field + FreeAlgebra + FiniteRing,
794        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
795        R: RingStore,
796        V: VectorView<El<R>>,
797        C: ConvolutionAlgorithm<R::Type>,
798        A: Allocator + Clone,
799        FreeAlgebraImplBase<R, V, A, C>: CanIsoFromTo<Impl::Type>
800{
801    type Isomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanIsoFromTo<Impl::Type>>::Isomorphism;
802
803    fn has_canonical_iso(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Isomorphism> {
804        self.has_canonical_iso(from.base.get_ring())
805    }
806    
807    fn map_out(&self, from: &GaloisFieldBase<Impl>, el: Self::Element, iso: &Self::Isomorphism) -> <GaloisFieldBase<Impl> as RingBase>::Element {
808        self.map_out(from.base.get_ring(), el, iso)
809    }
810}
811
812///
813/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
814/// 
815impl<Impl, R, A, V, C> CanIsoFromTo<GaloisFieldBase<Impl>> for AsFieldBase<FreeAlgebraImpl<R, V, A, C>>
816    where Impl: RingStore,
817        Impl::Type: Field + FreeAlgebra + FiniteRing,
818        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
819        R: RingStore,
820        R::Type: LinSolveRing,
821        V: VectorView<El<R>>,
822        C: ConvolutionAlgorithm<R::Type>,
823        A: Allocator + Clone,
824        FreeAlgebraImplBase<R, V, A, C>: CanIsoFromTo<Impl::Type>
825{
826    type Isomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanIsoFromTo<Impl::Type>>::Isomorphism;
827
828    fn has_canonical_iso(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Isomorphism> {
829        self.get_delegate().has_canonical_iso(from.base.get_ring())
830    }
831    
832    fn map_out(&self, from: &GaloisFieldBase<Impl>, el: Self::Element, iso: &Self::Isomorphism) -> <GaloisFieldBase<Impl> as RingBase>::Element {
833        self.get_delegate().map_out(from.base.get_ring(), self.delegate(el), iso)
834    }
835}
836
837#[cfg(test)]
838use test::Bencher;
839#[cfg(test)]
840use std::time::Instant;
841
842#[test]
843fn test_can_hom_from() {
844    #[allow(unused)]
845    fn assert_impl_CanHomFrom<From, To>()
846        where To: ?Sized + CanHomFrom<From>, From: ?Sized + RingBase 
847    {}
848    
849    #[allow(unused)]
850    fn FreeAlgebraImpl_wrap_unwrap_homs<R, V, A, C>()
851        where R: RingStore,
852            R::Type: SelfIso + LinSolveRing,
853            V: VectorView<El<R>>,
854            A: Allocator + Clone,
855            C: ConvolutionAlgorithm<R::Type>
856    {
857        assert_impl_CanHomFrom::<FreeAlgebraImplBase<R, V, A, C>, AsFieldBase<FreeAlgebraImpl<R, V, A, C>>>();
858    }
859
860    #[allow(unused)]
861    fn FreeAlgebraImpl_from_GaloisField<R, V, A, C>()
862        where R: RingStore,
863            R::Type: SelfIso + LinSolveRing + FiniteRing + Field + ZnRing,
864            V: VectorView<El<R>>,
865            A: Allocator + Clone,
866            C: ConvolutionAlgorithm<R::Type>
867    {
868        assert_impl_CanHomFrom::<GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>, AsFieldBase<FreeAlgebraImpl<R, V, A, C>>>();
869    }
870
871    #[allow(unused)]
872    fn GaloisField_from_GaloisField<R, V, A, C>()
873        where R: RingStore,
874            R::Type: SelfIso + LinSolveRing + FiniteRing + Field + ZnRing,
875            V: VectorView<El<R>>,
876            A: Allocator + Clone,
877            C: ConvolutionAlgorithm<R::Type>
878    {
879        assert_impl_CanHomFrom::<GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>, GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>>();
880    }
881}
882
883#[test]
884fn test_galois_field() {
885    let field = GaloisField::new(3, 1);
886    assert_eq!(3, field.elements().count());
887    crate::ring::generic_tests::test_ring_axioms(&field, field.elements());
888    crate::ring::generic_tests::test_self_iso(&field, field.elements());
889    crate::field::generic_tests::test_field_axioms(&field, field.elements());
890
891    let field = GaloisField::new(3, 2);
892    assert_eq!(9, field.elements().count());
893    crate::ring::generic_tests::test_ring_axioms(&field, field.elements());
894    crate::ring::generic_tests::test_self_iso(&field, field.elements());
895    crate::field::generic_tests::test_field_axioms(&field, field.elements());
896}
897
898#[test]
899fn test_principal_ideal_ring_axioms() {
900    let field = GaloisField::new(3, 2);
901    crate::pid::generic_tests::test_principal_ideal_ring_axioms(&field, field.elements());
902    crate::pid::generic_tests::test_euclidean_ring_axioms(&field, field.elements());
903}
904
905#[test]
906fn test_galois_field_even() {
907    for degree in 1..=9 {
908        let field = GaloisField::new_with_convolution(Zn::new(2).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
909        assert_eq!(degree, field.rank());
910        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
911    }
912}
913
914#[test]
915fn test_galois_field_odd() {
916    for degree in 1..=9 {
917        let field = GaloisField::new_with_convolution(Zn::new(3).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    for degree in 1..=9 {
923        let field = GaloisField::new_with_convolution(Zn::new(5).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
924        assert_eq!(degree, field.rank());
925        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
926    }
927}
928
929#[test]
930fn test_galois_field_no_trinomial() {
931    let field = GaloisField::new_with_convolution(Zn::new(2).as_field().ok().unwrap(), 24, Global, STANDARD_CONVOLUTION);
932    assert_eq!(24, field.rank());
933    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
934    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
935    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
936
937    let field = GaloisField::new_with_convolution(Zn::new(3).as_field().ok().unwrap(), 30, Global, STANDARD_CONVOLUTION);
938    assert_eq!(30, field.rank());
939    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
940    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
941    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
942
943    let field = GaloisField::new_with_convolution(Zn::new(17).as_field().ok().unwrap(), 32, Global, STANDARD_CONVOLUTION);
944    assert_eq!(32, field.rank());
945    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
946    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
947    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
948}
949
950#[bench]
951fn bench_create_galois_ring_2_14_96(bencher: &mut Bencher) {
952    bencher.iter(|| {
953        let field = GaloisField::new(2, 96);
954        let ring = field.get_ring().galois_ring(14);
955        assert_eq!(96, ring.rank());
956    });
957}
958
959#[test]
960#[ignore]
961fn test_galois_field_huge() {
962    let start = Instant::now();
963    let field = GaloisField::new(17, 2048);
964    _ = std::hint::black_box(field);
965    let end = Instant::now();
966    println!("Created GF(17^2048) in {} ms", (end - start).as_millis());
967}
feanor_math/rings/extension/galois_field.rs

feanor_math/rings/extension/
galois_field.rs
