feanor_math/rings/extension/
mod.rs

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

feanor_math/rings/extension/
mod.rs
