feanor_math/rings/extension/
mod.rs

1use super::field::{AsField, AsFieldBase};
2use super::poly::dense_poly::DensePolyRing;
3use super::poly::{PolyRing, PolyRingStore};
4use crate::algorithms::extension_ops;
5use crate::algorithms::linsolve::LinSolveRing;
6use crate::algorithms::poly_factor::FactorPolyField;
7use crate::divisibility::DivisibilityRing;
8use crate::field::*;
9use crate::homomorphism::*;
10use crate::pid::PrincipalIdealRing;
11use crate::ring::*;
12use crate::seq::*;
13use crate::wrapper::RingElementWrapper;
14
15/// Contains [`extension_impl::FreeAlgebraImpl`], an implementation of [`FreeAlgebra`] based
16/// on polynomial division.
17pub mod extension_impl;
18
19/// Contains [`galois_field::GaloisField`], an implementation of Galois fields.
20pub mod galois_field;
21
22/// Contains [`number_field::NumberField`], an implementation of number fields.
23pub mod number_field;
24
25/// A table of Conway polynomials, for standardized creation of finite fields.
26pub mod conway;
27
28/// A ring `R` that is an extension of a base ring `S`, generated by a single element
29/// that is algebraic resp. integral over `S`.
30///
31/// This is equivalent to rings generated by a single element that is a zero of a monic polynomial
32/// over the base ring. While sounding quite technical, this includes a wide class of important
33/// rings, like number fields or galois fields.
34/// One consequence of this is that `R` is a free `S`-module, with a basis given by the powers
35/// of [`FreeAlgebra::canonical_gen()`], which is where the name "free" comes from.
36///
37/// The main implementation is [`extension_impl::FreeAlgebraImpl`].
38///
39/// # Nontrivial Automorphisms
40///
41/// Rings of this form very often have nontrivial automorphisms. In order to simplify situations
42/// where morphisms or other objects are only unique up to isomorphism, canonical morphisms between
43/// rings of this type must also preserve the canonical generator.
44///
45/// # Examples
46///
47/// One of the most common use cases seems to be the implementation of finite fields (sometimes
48/// called galois fields).
49/// ```rust
50/// #![feature(allocator_api)]
51/// # use std::alloc::Global;
52/// # use feanor_math::assert_el_eq;
53/// # use feanor_math::ring::*;
54/// # use feanor_math::rings::zn::*;
55/// # use feanor_math::primitive_int::*;
56/// # use feanor_math::rings::extension::*;
57/// # use feanor_math::rings::extension::extension_impl::*;
58/// # use feanor_math::algorithms::convolution::*;
59/// # use feanor_math::field::FieldStore;
60/// # use feanor_math::divisibility::*;
61/// # use feanor_math::rings::finite::*;
62/// // we have to decide for an implementation of the prime field
63/// let prime_field = zn_static::Fp::<3>::RING;
64/// let galois_field = FreeAlgebraImpl::new(prime_field, 3, [2, 1]);
65/// // this is now the finite field with 27 elements, or F_27 or GF(27) since X^3 + 2X + 1 is irreducible modulo 3
66/// let galois_field = galois_field.as_field().ok().unwrap();
67/// assert_eq!(Some(27), galois_field.size(&StaticRing::<i64>::RING));
68/// for x in galois_field.elements() {
69///     if !galois_field.is_zero(&x) {
70///         let inv_x = galois_field.div(&galois_field.one(), &x);
71///         assert_el_eq!(galois_field, galois_field.one(), galois_field.mul(x, inv_x));
72///     }
73/// }
74/// // since galois fields are so important, an efficient construction is provided by feanor-math
75/// let galois_field_2 = galois_field::GaloisField::new_with_convolution(prime_field, 3, Global, STANDARD_CONVOLUTION);
76/// // note that the generating polynomial might be different, so it is not necessarily the "same" ring
77/// assert!(galois_field_2.can_iso(&galois_field).is_none());
78/// ```
79pub trait FreeAlgebra: RingExtension {
80    /// Type of the canonical-basis representation of a ring element, as returned by
81    /// [`FreeAlgebra::wrt_canonical_basis()`].
82    type VectorRepresentation<'a>: VectorFn<El<Self::BaseRing>>
83    where
84        Self: 'a;
85
86    /// Returns the fixed element that generates this ring as a free module over the base ring.
87    fn canonical_gen(&self) -> Self::Element;
88
89    /// Returns the rank of this ring as a free module over the base ring.
90    fn rank(&self) -> usize;
91
92    /// Returns the representation of the element w.r.t. the canonical basis, that is the basis
93    /// given by the powers `x^i` where `x` is the canonical generator given by
94    /// [`FreeAlgebra::canonical_gen()`] and `i` goes from `0` to `rank - 1`.
95    ///
96    /// In this sense, this is the opposite function to [`FreeAlgebra::from_canonical_basis()`].
97    fn wrt_canonical_basis<'a>(&'a self, el: &'a Self::Element) -> Self::VectorRepresentation<'a>;
98
99    /// Returns the element that has the given representation w.r.t. the canonical basis, that is
100    /// the basis given by the powers `x^i` where `x` is the canonical generator given by
101    /// [`FreeAlgebra::canonical_gen()`] and `i` goes from `0` to `rank - 1`.
102    ///
103    /// In this sense, this is the opposite function to [`FreeAlgebra::wrt_canonical_basis()`].
104    fn from_canonical_basis<V>(&self, vec: V) -> Self::Element
105    where
106        V: IntoIterator<Item = El<Self::BaseRing>>,
107        V::IntoIter: DoubleEndedIterator,
108    {
109        let mut given_len = 0;
110        let x = self.canonical_gen();
111        let mut result = self.zero();
112        for c in vec.into_iter().rev() {
113            self.mul_assign_ref(&mut result, &x);
114            self.add_assign(&mut result, self.from(c));
115            given_len += 1;
116        }
117        assert_eq!(given_len, self.rank());
118        return result;
119    }
120
121    /// Multiplies the given element by the `power`-th power of the canonical generator
122    /// of this ring, as given by [`FreeAlgebra::canonical_gen()`].
123    fn mul_assign_gen_power(&self, el: &mut Self::Element, power: usize) {
124        self.mul_assign(el, RingRef::new(self).pow(self.canonical_gen(), power));
125    }
126
127    /// Like [`FreeAlgebra::from_canonical_basis()`], this computes the sum `sum_i vec[i] * x^i`
128    /// where `x` is the canonical generator given by [`FreeAlgebra::canonical_gen()`]. Unlike
129    /// [`FreeAlgebra::from_canonical_basis()`], `vec` can return any number elements.
130    fn from_canonical_basis_extended<V>(&self, vec: V) -> Self::Element
131    where
132        V: IntoIterator<Item = El<Self::BaseRing>>,
133    {
134        extension_ops::from_canonical_basis_extended(self, vec)
135    }
136
137    /// Computes the characteristic polynomial of the given element.
138    ///
139    /// The characteristic polynomial is `det(XI - B)`, where `B` is the
140    /// matrix representation of the given element `b`, or equivalently the
141    /// matrix representation of the multiplication-by-`b` map `R^n -> R^n`.
142    fn charpoly<P, H>(&self, el: &Self::Element, poly_ring: P, hom: H) -> El<P>
143    where
144        P: RingStore,
145        P::Type: PolyRing,
146        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: LinSolveRing,
147        H: Homomorphism<<Self::BaseRing as RingStore>::Type, <<P::Type as RingExtension>::BaseRing as RingStore>::Type>,
148    {
149        extension_ops::charpoly(self, el, poly_ring, hom)
150    }
151
152    /// Computes the (or a) minimal polynomial of the given element.
153    ///
154    /// The minimal polynomial is the monic polynomial of minimal degree that
155    /// has the given value as a root. Its degree is always at least 1 and at
156    /// most [`FreeAlgebra::rank()`]. If the base ring is a principal ideal domain,
157    /// then the minimal polynomial is unique.
158    ///
159    /// Note that the existence of the minimal polynomial is a consequence of the
160    /// Cayley-Hamilton theorem, i.e. `det(XI - A)(A) = 0` for a square matrix over
161    /// any ring `R`. In particular, representing element of the ring `R[a]` a matrices
162    /// over `R`, we find that `det(XI - B)(b) = 0` for any element `b`, thus `b` must
163    /// be the root of a monic polynomial of degree `<= n`.
164    fn minpoly<P, H>(&self, el: &Self::Element, poly_ring: P, hom: H) -> El<P>
165    where
166        P: RingStore,
167        P::Type: PolyRing,
168        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: LinSolveRing,
169        H: Homomorphism<<Self::BaseRing as RingStore>::Type, <<P::Type as RingExtension>::BaseRing as RingStore>::Type>,
170    {
171        extension_ops::minpoly(self, el, poly_ring, hom)
172    }
173
174    /// Computes the trace of an element `a` in this ring extension, which is defined as the
175    /// matrix trace of the multiplication-by-`a` map.
176    ///
177    /// In nice extensions, the trace has many characterizations. For example, in a Galois
178    /// field extension, it is the sum of `sigma(a)` as `sigma` runs through the Galois group
179    /// of the extension. It is also equal to +/- the second largest coefficient of the
180    /// characteristic polynomial of the element.
181    fn trace(&self, el: Self::Element) -> El<Self::BaseRing> {
182        let mut current = el;
183        let generator = self.canonical_gen();
184        return self.base_ring().sum((0..self.rank()).map(|i| {
185            let result = self.wrt_canonical_basis(&current).at(i);
186            self.mul_assign_ref(&mut current, &generator);
187            return result;
188        }));
189    }
190
191    /// Computes the discriminant of the canonical basis of this ring extension,
192    /// which is defined as the determinant of the trace matrix `(Tr(a^(i + j)))`,
193    /// where `a` is the canonical generator of this ring extension.
194    ///
195    /// Note that the discriminant in this sense depends on the choice of the canonical
196    /// generator. In particular, this is usually different from the discriminant of an
197    /// algebraic number field, since that is defined as the discriminant w.r.t. the basis
198    /// that generates the maximal order. On the other hand, this means that if this ring
199    /// is an order in number field, this discriminant is exactly the discriminant of the
200    /// order as considered in algebraic number theory.
201    fn discriminant(&self) -> El<Self::BaseRing>
202    where
203        <Self::BaseRing as RingStore>::Type: PrincipalIdealRing,
204    {
205        extension_ops::discriminant(self)
206    }
207}
208
209/// [`RingStore`] for [`FreeAlgebra`].
210pub trait FreeAlgebraStore: RingStore
211where
212    Self::Type: FreeAlgebra,
213{
214    delegate! { FreeAlgebra, fn canonical_gen(&self) -> El<Self> }
215    delegate! { FreeAlgebra, fn rank(&self) -> usize }
216    delegate! { FreeAlgebra, fn trace(&self, el: El<Self>) -> El<<Self::Type as RingExtension>::BaseRing> }
217    delegate! { FreeAlgebra, fn mul_assign_gen_power(&self, el: &mut El<Self>, power: usize) -> () }
218
219    /// See [`FreeAlgebra::wrt_canonical_basis()`].
220    fn wrt_canonical_basis<'a>(&'a self, el: &'a El<Self>) -> <Self::Type as FreeAlgebra>::VectorRepresentation<'a> {
221        self.get_ring().wrt_canonical_basis(el)
222    }
223
224    /// See [`FreeAlgebra::from_canonical_basis()`].
225    fn from_canonical_basis<V>(&self, vec: V) -> El<Self>
226    where
227        V: IntoIterator<Item = El<<Self::Type as RingExtension>::BaseRing>>,
228        V::IntoIter: DoubleEndedIterator,
229    {
230        self.get_ring().from_canonical_basis(vec)
231    }
232
233    /// See [`FreeAlgebra::from_canonical_basis_extended()`].
234    fn from_canonical_basis_extended<V>(&self, vec: V) -> El<Self>
235    where
236        V: IntoIterator<Item = El<<Self::Type as RingExtension>::BaseRing>>,
237    {
238        self.get_ring().from_canonical_basis_extended(vec)
239    }
240
241    /// Returns the generating polynomial of this ring, i.e. the monic polynomial `f(X)` such that
242    /// this ring is isomorphic to `R[X]/(f(X))`, where `R` is the base ring.
243    fn generating_poly<P, H>(&self, poly_ring: P, hom: H) -> El<P>
244    where
245        P: PolyRingStore,
246        P::Type: PolyRing,
247        H: Homomorphism<
248                <<Self::Type as RingExtension>::BaseRing as RingStore>::Type,
249                <<P::Type as RingExtension>::BaseRing as RingStore>::Type,
250            >,
251    {
252        assert!(hom.domain().get_ring() == self.base_ring().get_ring());
253        poly_ring.sub(
254            poly_ring.from_terms([(poly_ring.base_ring().one(), self.rank())]),
255            self.poly_repr(&poly_ring, &self.pow(self.canonical_gen(), self.rank()), hom),
256        )
257    }
258
259    /// If this ring is a field, returns a wrapper around this ring that implements
260    /// [`crate::field::FieldStore`].
261    ///
262    /// For details, see [`crate::rings::field::AsField`].
263    fn as_field(self) -> Result<AsField<Self>, Self>
264    where
265        Self::Type: DivisibilityRing,
266        <<Self::Type as RingExtension>::BaseRing as RingStore>::Type: Field + FactorPolyField,
267    {
268        let poly_ring = DensePolyRing::new(self.base_ring(), "X");
269        if <_ as FactorPolyField>::factor_poly(
270            &poly_ring,
271            &self.generating_poly(&poly_ring, self.base_ring().identity()),
272        )
273        .0
274        .len()
275            > 1
276        {
277            return Err(self);
278        } else {
279            return Ok(RingValue::from(AsFieldBase::promise_is_perfect_field(self)));
280        }
281    }
282
283    /// Returns the polynomial representation of the given element `y`, i.e. the polynomial `f(X)`
284    /// of degree at most [`FreeAlgebraStore::rank()`] such that `f(x) = y`, where `y` is the
285    /// canonical generator of this ring, as given by [`FreeAlgebraStore::canonical_gen()`].
286    fn poly_repr<P, H>(&self, to: P, el: &El<Self>, hom: H) -> El<P>
287    where
288        P: PolyRingStore,
289        P::Type: PolyRing,
290        H: Homomorphism<
291                <<Self::Type as RingExtension>::BaseRing as RingStore>::Type,
292                <<P::Type as RingExtension>::BaseRing as RingStore>::Type,
293            >,
294    {
295        let coeff_vec = self.wrt_canonical_basis(el);
296        to.from_terms(
297            (0..self.rank())
298                .map(|i| coeff_vec.at(i))
299                .enumerate()
300                .filter(|(_, x)| !self.base_ring().is_zero(x))
301                .map(|(j, x)| (hom.map(x), j)),
302        )
303    }
304
305    /// Computes the discriminant of the canonical basis of this ring extension,
306    /// which is defined as the determinant of the trace matrix `(Tr(a^(i + j)))`,
307    /// where `a` is the canonical generator of this ring extension.
308    ///
309    /// See also [`FreeAlgebra::discriminant()`].
310    fn discriminant(&self) -> El<<Self::Type as RingExtension>::BaseRing>
311    where
312        <<Self::Type as RingExtension>::BaseRing as RingStore>::Type: PrincipalIdealRing,
313    {
314        self.get_ring().discriminant()
315    }
316
317    /// See also [`FreeAlgebra::charpoly()`].
318    fn charpoly<P, H>(&self, el: &El<Self>, poly_ring: P, hom: H) -> El<P>
319    where
320        P: RingStore,
321        P::Type: PolyRing,
322        <<P::Type as RingExtension>::BaseRing as RingStore>::Type: LinSolveRing,
323        H: Homomorphism<
324                <<Self::Type as RingExtension>::BaseRing as RingStore>::Type,
325                <<P::Type as RingExtension>::BaseRing as RingStore>::Type,
326            >,
327    {
328        self.get_ring().charpoly(el, poly_ring, hom)
329    }
330
331    /// Temporarily wraps the canonical generator in a [`RingElementWrapper`], for more
332    /// natural creation of ring elements.
333    #[stability::unstable(feature = "enable")]
334    fn with_wrapped_generator<'a, F, const M: usize>(&'a self, f: F) -> [El<Self>; M]
335    where
336        F: FnOnce(&RingElementWrapper<&'a Self>) -> [RingElementWrapper<&'a Self>; M],
337    {
338        let wrapped_indet = RingElementWrapper::new(self, self.canonical_gen());
339        let mut result_it = f(&wrapped_indet).into_iter();
340        return std::array::from_fn(|_| result_it.next().unwrap().unwrap());
341    }
342}
343
344impl<R: RingStore> FreeAlgebraStore for R where R::Type: FreeAlgebra {}
345
346#[stability::unstable(feature = "enable")]
347pub struct FreeAlgebraHom<R, S>
348where
349    R: RingStore,
350    R::Type: FreeAlgebra,
351    S: RingStore,
352    S::Type: FreeAlgebra,
353    <S::Type as RingExtension>::BaseRing: RingStore<Type = <<R::Type as RingExtension>::BaseRing as RingStore>::Type>,
354{
355    from: R,
356    to: S,
357    image_of_generator: El<S>,
358}
359
360impl<R> FreeAlgebraHom<R, R>
361where
362    R: RingStore + Clone,
363    R::Type: FreeAlgebra,
364{
365    #[stability::unstable(feature = "enable")]
366    pub fn identity(ring: R) -> Self {
367        Self {
368            image_of_generator: ring.canonical_gen(),
369            from: ring.clone(),
370            to: ring,
371        }
372    }
373}
374
375impl<R, S> FreeAlgebraHom<R, S>
376where
377    R: RingStore,
378    R::Type: FreeAlgebra,
379    S: RingStore,
380    S::Type: FreeAlgebra,
381    <S::Type as RingExtension>::BaseRing: RingStore<Type = <<R::Type as RingExtension>::BaseRing as RingStore>::Type>,
382{
383    /// Creates a new [`FreeAlgebraHom`] from `R` to `S`, mapping the canonical
384    /// generator of `R` to the given element of `S`. This assumes that the resulting
385    /// homomorphism is well-defined, i.e. the generating polynomial of `R` evaluated
386    /// at `image_of_generator` gives zero in `S`.
387    ///
388    /// The checked variant of this function is [`FreeAlgebraHom::new()`].
389    #[stability::unstable(feature = "enable")]
390    pub fn promise_is_well_defined(from: R, to: S, image_of_generator: El<S>) -> Self {
391        assert!(from.base_ring().get_ring() == to.base_ring().get_ring());
392        Self {
393            from,
394            to,
395            image_of_generator,
396        }
397    }
398
399    /// Creates a new [`FreeAlgebraHom`] from `R` to `S`, mapping the canonical
400    /// generator of `R` to the given element of `S`.
401    ///
402    /// As opposed to [`FreeAlgebraHom::promise_is_well_defined()`], this function
403    /// checks that the resulting homomorphism is well-defined.
404    #[stability::unstable(feature = "enable")]
405    pub fn new(from: R, to: S, image_of_generator: El<S>) -> Self {
406        assert!(from.base_ring().get_ring() == to.base_ring().get_ring());
407        let poly_ring = DensePolyRing::new(to.base_ring(), "X");
408        assert!(to.is_zero(&poly_ring.evaluate(
409            &from.generating_poly(&poly_ring, poly_ring.base_ring().identity()),
410            &image_of_generator,
411            to.inclusion()
412        )));
413        Self {
414            from,
415            to,
416            image_of_generator,
417        }
418    }
419
420    /// Consumes this object, producing the domain ring store, the codomain ring store
421    /// and the image of the canonical generator of the domain number field.
422    #[stability::unstable(feature = "enable")]
423    pub fn destruct(self) -> (R, S, El<S>) { (self.from, self.to, self.image_of_generator) }
424}
425
426impl<R, S> Homomorphism<R::Type, S::Type> for FreeAlgebraHom<R, S>
427where
428    R: RingStore,
429    R::Type: FreeAlgebra,
430    S: RingStore,
431    S::Type: FreeAlgebra,
432    <S::Type as RingExtension>::BaseRing: RingStore<Type = <<R::Type as RingExtension>::BaseRing as RingStore>::Type>,
433{
434    type DomainStore = R;
435    type CodomainStore = S;
436
437    fn domain(&self) -> &Self::DomainStore { &self.from }
438
439    fn codomain(&self) -> &Self::CodomainStore { &self.to }
440
441    fn map(&self, x: El<R>) -> El<S> { self.map_ref(&x) }
442
443    fn map_ref(&self, x: &El<R>) -> El<S> {
444        let poly_ring = DensePolyRing::new(self.to.base_ring(), "X");
445        return poly_ring.evaluate(
446            &self.from.poly_repr(&poly_ring, x, self.to.base_ring().identity()),
447            &self.image_of_generator,
448            self.to.inclusion(),
449        );
450    }
451}
452
453#[cfg(any(test, feature = "generic_tests"))]
454pub mod generic_tests {
455    use super::*;
456
457    pub fn test_free_algebra_axioms<R: FreeAlgebraStore>(ring: R)
458    where
459        R::Type: FreeAlgebra,
460    {
461        let x = ring.canonical_gen();
462        let n = ring.rank();
463
464        let xn_original = ring.pow(ring.clone_el(&x), n);
465        let xn_vec = ring.wrt_canonical_basis(&xn_original);
466        let xn = ring.sum(Iterator::map(0..n, |i| {
467            ring.mul(ring.inclusion().map(xn_vec.at(i)), ring.pow(ring.clone_el(&x), i))
468        }));
469        assert_el_eq!(ring, xn_original, xn);
470
471        let x_n_1_vec_expected = (0..n).map_fn(|i| {
472            if i > 0 {
473                ring.base_ring()
474                    .add(ring.base_ring().mul(xn_vec.at(n - 1), xn_vec.at(i)), xn_vec.at(i - 1))
475            } else {
476                ring.base_ring().mul(xn_vec.at(n - 1), xn_vec.at(0))
477            }
478        });
479        let x_n_1 = ring.pow(ring.clone_el(&x), n + 1);
480        let x_n_1_vec_actual = ring.wrt_canonical_basis(&x_n_1);
481        for i in 0..n {
482            assert_el_eq!(ring.base_ring(), x_n_1_vec_expected.at(i), x_n_1_vec_actual.at(i));
483        }
484
485        // test basis wrt_canonical_basis linearity and compatibility
486        // from_canonical_basis/wrt_canonical_basis
487        for i in (0..ring.rank()).step_by(3) {
488            for j in (1..ring.rank()).step_by(5) {
489                if i == j {
490                    continue;
491                }
492                let element = ring.from_canonical_basis((0..n).map(|k| {
493                    if k == i {
494                        ring.base_ring().one()
495                    } else if k == j {
496                        ring.base_ring().int_hom().map(2)
497                    } else {
498                        ring.base_ring().zero()
499                    }
500                }));
501                let expected = ring.add(
502                    ring.pow(ring.clone_el(&x), i),
503                    ring.int_hom().mul_map(ring.pow(ring.clone_el(&x), j), 2),
504                );
505                assert_el_eq!(ring, expected, element);
506                let element_vec = ring.wrt_canonical_basis(&expected);
507                for k in 0..ring.rank() {
508                    if k == i {
509                        assert_el_eq!(ring.base_ring(), ring.base_ring().one(), element_vec.at(k));
510                    } else if k == j {
511                        assert_el_eq!(ring.base_ring(), ring.base_ring().int_hom().map(2), element_vec.at(k));
512                    } else {
513                        assert_el_eq!(ring.base_ring(), ring.base_ring().zero(), element_vec.at(k));
514                    }
515                }
516            }
517        }
518
519        // test basis mul_assign_gen_power
520        for i in (0..ring.rank()).step_by(3) {
521            for j in (0..ring.rank()).step_by(5) {
522                let element = ring.add(ring.pow(ring.canonical_gen(), i), ring.one());
523                let mut actual = ring.clone_el(&element);
524                ring.mul_assign_gen_power(&mut actual, j);
525                assert_el_eq!(ring, ring.mul(element, ring.pow(ring.canonical_gen(), j)), actual);
526            }
527        }
528    }
529}
feanor_math/rings/extension/mod.rs

feanor_math/rings/extension/
mod.rs
