feanor_math/rings/extension/
galois_field.rs

1use std::alloc::{Allocator, Global};
2
3use extension_impl::FreeAlgebraImplBase;
4use sparse::SparseMapVector;
5use zn_64::Zn;
6
7use crate::algorithms::convolution::ConvolutionAlgorithm;
8use crate::algorithms::convolution::KaratsubaAlgorithm;
9use crate::algorithms::convolution::KaratsubaHint;
10use crate::algorithms::convolution::STANDARD_CONVOLUTION;
11use crate::algorithms::eea::signed_gcd;
12use crate::algorithms::poly_gcd::finite::poly_squarefree_part_finite_field;
13use crate::algorithms::int_factor::factor;
14use crate::algorithms::int_factor::is_prime_power;
15use crate::algorithms::matmul::ComputeInnerProduct;
16use crate::algorithms::matmul::StrassenHint;
17use crate::algorithms::poly_gcd::PolyTFracGCDRing;
18use crate::algorithms::unity_root::*;
19use crate::delegate::DelegateRing;
20use crate::delegate::DelegateRingImplFiniteRing;
21use crate::divisibility::DivisibilityRingStore;
22use crate::divisibility::Domain;
23use crate::field::*;
24use crate::pid::PrincipalIdealRing;
25use crate::rings::extension::extension_impl::FreeAlgebraImpl;
26use crate::rings::finite::*;
27use crate::algorithms::convolution::fft::*;
28use crate::algorithms::poly_factor::cantor_zassenhaus;
29use crate::pid::EuclideanRing;
30use crate::primitive_int::StaticRing;
31use crate::primitive_int::StaticRingBase;
32use crate::rings::field::AsField;
33use crate::rings::field::AsFieldBase;
34use crate::rings::local::AsLocalPIR;
35use crate::rings::local::AsLocalPIRBase;
36use crate::rings::poly::dense_poly::DensePolyRing;
37use crate::rings::poly::PolyRing;
38use crate::rings::zn::*;
39use crate::ring::*;
40use crate::rings::extension::*;
41use crate::integer::*;
42
43fn filter_irreducible<R, P>(poly_ring: P, mod_f_ring: R, degree: usize) -> Option<El<P>>
44    where P: RingStore,
45        P::Type: PolyRing + EuclideanRing,
46        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + FiniteRing + Field,
47        R: RingStore,
48        R::Type: FreeAlgebra,
49        <R::Type as RingExtension>::BaseRing: RingStore<Type = <<P::Type as RingExtension>::BaseRing as RingStore>::Type>
50{
51    let f = mod_f_ring.generating_poly(&poly_ring, &poly_ring.base_ring().identity());
52    let squarefree_part = poly_squarefree_part_finite_field(&poly_ring, &f);
53    if poly_ring.degree(&squarefree_part) != Some(degree) {
54        return None;
55    }
56    if !cantor_zassenhaus::squarefree_is_irreducible_base(&poly_ring, &mod_f_ring) {
57        return None;
58    }
59    return Some(mod_f_ring.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
60}
61
62///
63/// Tries to find a "small" irreducible polynomial of given degree.
64/// 
65/// "small" is not well-defined, but can mean sparse, or having a small `deg(f - lt(f))`.
66/// Both will lead to more efficient arithmetic in the ring `k[X]/(f)`. However, in general
67/// finding a very small `f` is hard, thus we use heuristics.
68/// 
69fn find_small_irreducible_poly_base<P, C>(poly_ring: P, degree: usize, convolution: C, rng: &mut oorandom::Rand64) -> El<P>
70    where P: RingStore,
71        P::Type: PolyRing + EuclideanRing,
72        <P::Type as RingExtension>::BaseRing: Copy,
73        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>,
74        C: ConvolutionAlgorithm<<<P::Type as RingExtension>::BaseRing as RingStore>::Type>
75{
76    let Fp = *poly_ring.base_ring();
77    let create_mod_f_ring = |f: &El<P>| {
78        let mut f_body = SparseMapVector::new(degree, poly_ring.base_ring());
79        for (c, i) in poly_ring.terms(f) {
80            if i != degree {
81                *f_body.at_mut(i) = poly_ring.base_ring().negate(poly_ring.base_ring().clone_el(c));
82            }
83        }
84        return FreeAlgebraImpl::new_with(Fp, degree, f_body, "θ", Global, &convolution);
85    };
86
87    if degree > 3 {
88
89        // first try trinomials, they seem to have a good chance of being irreducible
90        for _ in 0..16 {
91            let i = (StaticRing::<i64>::RING.get_uniformly_random(&(degree as i64 - 1), || rng.rand_u64()) + 1) as usize;
92            let a = Fp.random_element(|| rng.rand_u64());
93            let b = Fp.random_element(|| rng.rand_u64());
94            let f = poly_ring.from_terms([(a, 0), (b, i), (Fp.one(), degree)].into_iter());
95            if let Some(result)  = filter_irreducible(&poly_ring, create_mod_f_ring(&f), degree) {
96                return result;
97            }
98        }
99    
100        // next, check for cases where we can take `small_poly(X^high_power)`; these cases are characterized by the
101        // fact that we have `degree = small_d * large_d` with `large_d | #F_(q^small_d)*`
102        let ZZbig = BigIntRing::RING;
103        let ZZ = StaticRing::<i64>::RING;
104    
105        let p = Fp.size(&ZZbig).unwrap();
106        let mut small_d = 1;
107        let Fq_star_order = ZZbig.sub(ZZbig.pow(ZZbig.clone_el(&p), small_d as usize), ZZbig.one());
108        let mut large_d = int_cast(signed_gcd(Fq_star_order, int_cast(degree as i64 / small_d, ZZbig, StaticRing::<i64>::RING), ZZbig), ZZ, ZZbig);
109        let mut increased_small_d = true;
110        while increased_small_d {
111            increased_small_d = false;
112            // use a greedy approach, just add a factor to small_d if it makes large_d larger
113            for (k, _) in factor(&ZZ, degree as i64 / small_d) {
114                let new_small_d = small_d * k;
115                let Fq_star_order = ZZbig.sub(ZZbig.pow(ZZbig.clone_el(&p), new_small_d as usize), ZZbig.one());
116                let new_large_d = int_cast(signed_gcd(Fq_star_order, int_cast(degree as i64 / new_small_d, ZZbig, StaticRing::<i64>::RING), ZZbig), ZZ, ZZbig);
117                if new_large_d > large_d {
118                    small_d = new_small_d;
119                    large_d = new_large_d;
120                    increased_small_d = true;
121                    break;
122                }
123            }
124        }
125        small_d = degree as i64 / large_d;
126        if large_d != 1 {
127            let Fq_star_order = ZZbig.sub(ZZbig.pow(ZZbig.clone_el(&p), small_d as usize), ZZbig.one());
128            // careful here to not get an infinite generic argument recursion
129            let Fq = GaloisField::new_internal(Fp, small_d as usize, Global, &convolution);
130            // the primitive element of `Fq` clearly has no `k`-th root, for every `k | large_d` since `large_d | #Fq*`;
131            // hence we can use `MinPoly(primitive_element)(X^large_d)`
132            let primitive_element = if is_prim_root_of_unity_gen(&Fq, &Fq.canonical_gen(), &Fq_star_order, ZZbig) {
133                Fq.canonical_gen()
134            } else {
135                get_prim_root_of_unity_gen(&Fq, &Fq_star_order, ZZbig).unwrap()
136            };
137            // 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,
138            // however it is not guaranteed that this would indeed generate the field
139            let FqX = DensePolyRing::new(&Fq, "X");
140            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())));
141            let minpoly_Fp = poly_ring.from_terms(FqX.terms(&minpoly).map(|(c, i)| {
142                let c_wrt_basis = Fq.wrt_canonical_basis(c);
143                assert!(c_wrt_basis.iter().skip(1).all(|x| Fp.is_zero(&x)));
144                return (c_wrt_basis.at(0), i);
145            }));
146            let f = poly_ring.evaluate(&minpoly_Fp, &poly_ring.from_terms([(Fp.one(), large_d as usize)].into_iter()), &poly_ring.inclusion());
147            return f;
148        }
149    }
150
151    // fallback, just generate a random irreducible polynomial
152    loop {
153        let f = poly_ring.from_terms((0..degree).map(|i| (Fp.random_element(|| rng.rand_u64()), i)).chain([(Fp.one(), degree)].into_iter()));
154        if let Some(result) = filter_irreducible(&poly_ring, create_mod_f_ring(&f), degree) {
155            return result;
156        }
157    }
158}
159
160fn find_small_irreducible_poly<P>(poly_ring: P, degree: usize, rng: &mut oorandom::Rand64) -> El<P>
161    where P: RingStore,
162        P::Type: PolyRing + EuclideanRing,
163        <P::Type as RingExtension>::BaseRing: Copy,
164        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>
165{
166    static_assert_impls!(<<P::Type as RingExtension>::BaseRing as RingStore>::Type: PolyTFracGCDRing);
167    
168    let log2_modulus = poly_ring.base_ring().integer_ring().abs_log2_ceil(poly_ring.base_ring().modulus()).unwrap();
169    let fft_convolution = FFTConvolution::new_with(Global);
170    if fft_convolution.has_sufficient_precision(StaticRing::<i64>::RING.abs_log2_ceil(&(degree as i64)).unwrap() + 1, log2_modulus) {
171        find_small_irreducible_poly_base(
172            &poly_ring,
173            degree,
174            <FFTConvolutionZn as From<_>>::from(fft_convolution),
175            rng
176        )
177    } else {
178        find_small_irreducible_poly_base(
179            &poly_ring,
180            degree,
181            STANDARD_CONVOLUTION,
182            rng
183        )
184    }
185}
186
187///
188/// Implementation of a galois field `GF(p^e)`; Also known as galois field, and sometimes denoted by `Fq` where `q = p^e`. 
189/// 
190/// There exists a finite field with `q` elements if and only if `q = p^e` is a prime power. In these cases,
191/// this struct provides an implementation of arithmetic in these fields. Note that since those fields are always finite-degree
192/// extensions of `Z/pZ`, they can also be used by creating a suitable instance of [`super::extension_impl::FreeAlgebraImpl`]. In fact,
193/// this is the way the old implementation of galois fields was designed. However, providing a new type can provide both 
194/// ergonomic and performance benefits, and also gives better encapsulation.
195/// 
196/// # Example
197/// 
198/// The easiest way to create a Galois field is by using `new()`:
199/// ```
200/// # use feanor_math::ring::*;
201/// # use feanor_math::rings::extension::*;
202/// # use feanor_math::rings::finite::*;
203/// # use feanor_math::homomorphism::*;
204/// # use feanor_math::primitive_int::*;
205/// # use feanor_math::rings::extension::galois_field::*;
206/// let F25: GaloisField = GaloisField::new(5, 2);
207/// assert_eq!(5, F25.characteristic(&StaticRing::<i64>::RING).unwrap());
208/// assert_eq!(2, F25.rank());
209/// ```
210/// More configurations are possible using [`GaloisField::new_with()`] or [`GaloisField::create()`].
211/// 
212/// We also support conversion to and from a plain [`super::extension_impl::FreeAlgebraImpl`] representation.
213/// ```
214/// # use feanor_math::ring::*;
215/// # use feanor_math::rings::extension::*;
216/// # use feanor_math::rings::extension::extension_impl::*;
217/// # use feanor_math::rings::field::*;
218/// # use feanor_math::rings::finite::*;
219/// # use feanor_math::homomorphism::*;
220/// # use feanor_math::primitive_int::*;
221/// # use feanor_math::rings::extension::galois_field::*;
222/// let F25: GaloisField = GaloisField::new(5, 2);
223/// let raw_F25: AsField<FreeAlgebraImpl<_, _>> = F25.clone().into().unwrap_self();
224/// assert!(F25.can_iso(&raw_F25).is_some());
225/// ```
226/// The other way is slightly more dangerous, since at some point we either have to check, or assume
227/// that the extension ring is indeed a field.
228/// ```
229/// # use feanor_math::ring::*;
230/// # use feanor_math::rings::extension::*;
231/// # use feanor_math::rings::extension::extension_impl::*;
232/// # use feanor_math::rings::field::*;
233/// # use feanor_math::rings::finite::*;
234/// # use feanor_math::homomorphism::*;
235/// # use feanor_math::rings::zn::zn_64::*;
236/// # use feanor_math::rings::zn::*;
237/// # use feanor_math::primitive_int::*;
238/// # use feanor_math::rings::extension::galois_field::*;
239/// let base_ring = Zn::new(5).as_field().ok().unwrap();
240/// let raw_F25: FreeAlgebraImpl<_, _> = FreeAlgebraImpl::new(base_ring, 2, [base_ring.int_hom().map(2)]);
241/// let asfield_F25 = raw_F25.clone().as_field().ok().unwrap();
242/// // 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!
243/// let asfield_F25 = AsField::from(AsFieldBase::promise_is_field(raw_F25).ok().unwrap());
244/// let F25 = GaloisField::create(asfield_F25);
245/// assert!(F25.can_iso(&raw_F25).is_some());
246/// ```
247/// 
248/// # Choice of blanket implementations of [`CanHomFrom`]
249/// 
250/// As opposed to the more generic [`DelegateRing`]s, here I chose a "ping-pong" way
251/// of implementing [`CanHomFrom`] and [`CanIsoFromTo`] for [`GaloisFieldBase`] that is
252/// very powerful when we use the standard `Impl = AsField<FreeAlgebraImpl<_, _, _, _>>`.
253/// In particular, we implement `GaloisFieldBase<Impl>: CanHomFrom<S>` for all `S` with 
254/// `Impl: CanHomFrom<S>`. It is great that we can provide such a large class of blanket impls,
255/// however this impl will then conflict with (almost) all other impls - which is the reason
256/// why we don't do it e.g. for [`AsFieldBase`].
257/// 
258/// Instead, we complement it with just the impls `FreeAlgebraImplBase<_, _, _, _>: CanHomFrom<GaloisFieldBase<_>>`
259/// and `AsFieldBase<FreeAlgebraImpl<_, _, _, _>>: CanHomFrom<GaloisFieldBase<_>>`. This means
260/// that if `Impl = AsFieldBase<FreeAlgebraImpl<_, _, _, _>>`, together with the blanket implementation,
261/// it gives the very much desired self-isomorphism `GaloisFieldBase<_>: CanHomFrom<GaloisFieldBase<_>>`.
262/// The only downside of this approach is that `GaloisFieldBase` does not have a canonical self-isomorphism
263/// anymore if a nonstandard `Impl` is chosen - which I believe will be very rarely the case in practice.
264/// 
265#[repr(transparent)]
266pub struct GaloisFieldBase<Impl>
267    where Impl: RingStore,
268        Impl::Type: Field + FreeAlgebra + FiniteRing,
269        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
270{
271    base: Impl
272}
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    /// ```
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    /// ```
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> KaratsubaHint for GaloisFieldBase<Impl>
629    where Impl: RingStore,
630        Impl::Type: Field + FreeAlgebra + FiniteRing,
631        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
632{
633    fn karatsuba_threshold(&self) -> usize {
634        self.get_delegate().karatsuba_threshold()
635    }
636}
637
638impl<Impl> ComputeInnerProduct for GaloisFieldBase<Impl>
639    where Impl: RingStore,
640        Impl::Type: Field + FreeAlgebra + FiniteRing,
641        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field
642{
643    fn inner_product<I: Iterator<Item = (Self::Element, Self::Element)>>(&self, els: I) -> Self::Element {
644        self.rev_delegate(self.get_delegate().inner_product(els.map(|(a, b)| (self.delegate(a), self.delegate(b)))))
645    }
646
647    fn inner_product_ref<'a, I: Iterator<Item = (&'a Self::Element, &'a Self::Element)>>(&self, els: I) -> Self::Element
648        where Self::Element: 'a,
649            Self: 'a
650    {
651        self.rev_delegate(self.get_delegate().inner_product_ref(els.map(|(a, b)| (self.delegate_ref(a), self.delegate_ref(b)))))
652    }
653
654    fn inner_product_ref_fst<'a, I: Iterator<Item = (&'a Self::Element, Self::Element)>>(&self, els: I) -> Self::Element
655        where Self::Element: 'a,
656            Self: 'a
657    {
658        self.rev_delegate(self.get_delegate().inner_product_ref_fst(els.map(|(a, b)| (self.delegate_ref(a), self.delegate(b)))))
659    }
660}
661
662impl<Impl> StrassenHint 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 strassen_threshold(&self) -> usize {
668        self.get_delegate().strassen_threshold()
669    }
670}
671
672///
673/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
674/// 
675impl<Impl, S> CanHomFrom<S> for GaloisFieldBase<Impl>
676    where Impl: RingStore,
677        Impl::Type: Field + FreeAlgebra + FiniteRing + CanHomFrom<S>,
678        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
679        S: ?Sized + RingBase
680{
681    type Homomorphism = <Impl::Type as CanHomFrom<S>>::Homomorphism;
682
683    fn has_canonical_hom(&self, from: &S) -> Option<Self::Homomorphism> {
684        self.base.get_ring().has_canonical_hom(from)
685    }
686
687    fn map_in(&self, from: &S, el: <S as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
688        self.base.get_ring().map_in(from, el, hom)
689    }
690}
691
692///
693/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
694/// 
695impl<Impl, R, A, V, C> CanHomFrom<GaloisFieldBase<Impl>> for FreeAlgebraImplBase<R, V, A, C>
696    where Impl: RingStore,
697        Impl::Type: Field + FreeAlgebra + FiniteRing,
698        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
699        R: RingStore,
700        V: VectorView<El<R>>,
701        C: ConvolutionAlgorithm<R::Type>,
702        A: Allocator + Clone,
703        FreeAlgebraImplBase<R, V, A, C>: CanHomFrom<Impl::Type>
704{
705    type Homomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanHomFrom<Impl::Type>>::Homomorphism;
706
707    fn has_canonical_hom(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Homomorphism> {
708        self.has_canonical_hom(from.base.get_ring())
709    }
710
711    fn map_in(&self, from: &GaloisFieldBase<Impl>, el: <GaloisFieldBase<Impl> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
712        self.map_in(from.base.get_ring(), 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 AsFieldBase<FreeAlgebraImpl<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        R::Type: LinSolveRing,
725        V: VectorView<El<R>>,
726        C: ConvolutionAlgorithm<R::Type>,
727        A: Allocator + Clone,
728        FreeAlgebraImplBase<R, V, A, C>: CanHomFrom<Impl::Type>
729{
730    type Homomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanHomFrom<Impl::Type>>::Homomorphism;
731
732    fn has_canonical_hom(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Homomorphism> {
733        self.get_delegate().has_canonical_hom(from.base.get_ring())
734    }
735
736    fn map_in(&self, from: &GaloisFieldBase<Impl>, el: <GaloisFieldBase<Impl> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
737        self.rev_delegate(self.get_delegate().map_in(from.base.get_ring(), el, hom))
738    }
739}
740
741///
742/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
743/// 
744impl<Impl, S> CanIsoFromTo<S> for GaloisFieldBase<Impl>
745    where Impl: RingStore,
746        Impl::Type: Field + FreeAlgebra + FiniteRing + CanIsoFromTo<S>,
747        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
748        S: ?Sized + RingBase
749{
750    type Isomorphism = <Impl::Type as CanIsoFromTo<S>>::Isomorphism;
751
752    fn has_canonical_iso(&self, from: &S) -> Option<Self::Isomorphism> {
753        self.base.get_ring().has_canonical_iso(from)
754    }
755
756    fn map_out(&self, from: &S, el: Self::Element, iso: &Self::Isomorphism) -> <S as RingBase>::Element {
757        self.base.get_ring().map_out(from, el, iso)
758    }
759}
760
761///
762/// For the rationale which blanket implementations I chose, see the [`GaloisFieldBase`].
763/// 
764impl<Impl, R, A, V, C> CanIsoFromTo<GaloisFieldBase<Impl>> for FreeAlgebraImplBase<R, V, A, C>
765    where Impl: RingStore,
766        Impl::Type: Field + FreeAlgebra + FiniteRing,
767        <<Impl::Type as RingExtension>::BaseRing as RingStore>::Type: ZnRing + Field,
768        R: RingStore,
769        V: VectorView<El<R>>,
770        C: ConvolutionAlgorithm<R::Type>,
771        A: Allocator + Clone,
772        FreeAlgebraImplBase<R, V, A, C>: CanIsoFromTo<Impl::Type>
773{
774    type Isomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanIsoFromTo<Impl::Type>>::Isomorphism;
775
776    fn has_canonical_iso(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Isomorphism> {
777        self.has_canonical_iso(from.base.get_ring())
778    }
779    
780    fn map_out(&self, from: &GaloisFieldBase<Impl>, el: Self::Element, iso: &Self::Isomorphism) -> <GaloisFieldBase<Impl> as RingBase>::Element {
781        self.map_out(from.base.get_ring(), 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 AsFieldBase<FreeAlgebraImpl<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        R::Type: LinSolveRing,
794        V: VectorView<El<R>>,
795        C: ConvolutionAlgorithm<R::Type>,
796        A: Allocator + Clone,
797        FreeAlgebraImplBase<R, V, A, C>: CanIsoFromTo<Impl::Type>
798{
799    type Isomorphism = <FreeAlgebraImplBase<R, V, A, C> as CanIsoFromTo<Impl::Type>>::Isomorphism;
800
801    fn has_canonical_iso(&self, from: &GaloisFieldBase<Impl>) -> Option<Self::Isomorphism> {
802        self.get_delegate().has_canonical_iso(from.base.get_ring())
803    }
804    
805    fn map_out(&self, from: &GaloisFieldBase<Impl>, el: Self::Element, iso: &Self::Isomorphism) -> <GaloisFieldBase<Impl> as RingBase>::Element {
806        self.get_delegate().map_out(from.base.get_ring(), self.delegate(el), iso)
807    }
808}
809
810#[cfg(test)]
811use test::Bencher;
812#[cfg(test)]
813use std::time::Instant;
814
815#[test]
816fn test_can_hom_from() {
817    #[allow(unused)]
818    fn assert_impl_CanHomFrom<From, To>()
819        where To: ?Sized + CanHomFrom<From>, From: ?Sized + RingBase 
820    {}
821    
822    #[allow(unused)]
823    fn FreeAlgebraImpl_wrap_unwrap_homs<R, V, A, C>()
824        where R: RingStore,
825            R::Type: SelfIso + LinSolveRing,
826            V: VectorView<El<R>>,
827            A: Allocator + Clone,
828            C: ConvolutionAlgorithm<R::Type>
829    {
830        assert_impl_CanHomFrom::<FreeAlgebraImplBase<R, V, A, C>, AsFieldBase<FreeAlgebraImpl<R, V, A, C>>>();
831    }
832
833    #[allow(unused)]
834    fn FreeAlgebraImpl_from_GaloisField<R, V, A, C>()
835        where R: RingStore,
836            R::Type: SelfIso + LinSolveRing + FiniteRing + Field + ZnRing,
837            V: VectorView<El<R>>,
838            A: Allocator + Clone,
839            C: ConvolutionAlgorithm<R::Type>
840    {
841        assert_impl_CanHomFrom::<GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>, AsFieldBase<FreeAlgebraImpl<R, V, A, C>>>();
842    }
843
844    #[allow(unused)]
845    fn GaloisField_from_GaloisField<R, V, A, C>()
846        where R: RingStore,
847            R::Type: SelfIso + LinSolveRing + FiniteRing + Field + ZnRing,
848            V: VectorView<El<R>>,
849            A: Allocator + Clone,
850            C: ConvolutionAlgorithm<R::Type>
851    {
852        assert_impl_CanHomFrom::<GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>, GaloisFieldBase<AsField<FreeAlgebraImpl<R, V, A, C>>>>();
853    }
854}
855
856#[test]
857fn test_galois_field() {
858    let field = GaloisField::new(3, 1);
859    assert_eq!(3, field.elements().count());
860    crate::ring::generic_tests::test_ring_axioms(&field, field.elements());
861    crate::ring::generic_tests::test_self_iso(&field, field.elements());
862    crate::field::generic_tests::test_field_axioms(&field, field.elements());
863
864    let field = GaloisField::new(3, 2);
865    assert_eq!(9, field.elements().count());
866    crate::ring::generic_tests::test_ring_axioms(&field, field.elements());
867    crate::ring::generic_tests::test_self_iso(&field, field.elements());
868    crate::field::generic_tests::test_field_axioms(&field, field.elements());
869}
870
871#[test]
872fn test_principal_ideal_ring_axioms() {
873    let field = GaloisField::new(3, 2);
874    crate::pid::generic_tests::test_principal_ideal_ring_axioms(&field, field.elements());
875    crate::pid::generic_tests::test_euclidean_ring_axioms(&field, field.elements());
876}
877
878#[test]
879fn test_galois_field_even() {
880    for degree in 1..=9 {
881        let field = GaloisField::new_with(Zn::new(2).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
882        assert_eq!(degree, field.rank());
883        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
884    }
885}
886
887#[test]
888fn test_galois_field_odd() {
889    for degree in 1..=9 {
890        let field = GaloisField::new_with(Zn::new(3).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
891        assert_eq!(degree, field.rank());
892        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
893    }
894
895    for degree in 1..=9 {
896        let field = GaloisField::new_with(Zn::new(5).as_field().ok().unwrap(), degree, Global, STANDARD_CONVOLUTION);
897        assert_eq!(degree, field.rank());
898        assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
899    }
900}
901
902#[test]
903fn test_galois_field_no_trinomial() {
904    let field = GaloisField::new_with(Zn::new(2).as_field().ok().unwrap(), 24, Global, STANDARD_CONVOLUTION);
905    assert_eq!(24, field.rank());
906    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
907    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
908    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
909
910    let field = GaloisField::new_with(Zn::new(3).as_field().ok().unwrap(), 30, Global, STANDARD_CONVOLUTION);
911    assert_eq!(30, field.rank());
912    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
913    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
914    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
915
916    let field = GaloisField::new_with(Zn::new(17).as_field().ok().unwrap(), 32, Global, STANDARD_CONVOLUTION);
917    assert_eq!(32, field.rank());
918    let poly_ring = DensePolyRing::new(field.base_ring(), "X");
919    poly_ring.println(&field.generating_poly(&poly_ring, &poly_ring.base_ring().identity()));
920    assert!(field.into().unwrap_self().into().unwrap_self().as_field().is_ok());
921}
922
923#[bench]
924fn bench_create_galois_ring_2_14_96(bencher: &mut Bencher) {
925    bencher.iter(|| {
926        let field = GaloisField::new(2, 96);
927        let ring = field.get_ring().galois_ring(14);
928        assert_eq!(96, ring.rank());
929    });
930}
931
932#[test]
933#[ignore]
934fn test_galois_field_huge() {
935    let start = Instant::now();
936    let field = GaloisField::new(17, 2048);
937    _ = std::hint::black_box(field);
938    let end = Instant::now();
939    println!("Created GF(17^2048) in {} ms", (end - start).as_millis());
940}
feanor_math/rings/extension/galois_field.rs

feanor_math/rings/extension/
galois_field.rs
