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