feanor_math/rings/extension/
extension_impl.rs

1use std::alloc::Allocator;
2use std::alloc::Global;
3
4use serde::de::DeserializeSeed;
5use serde::Deserializer;
6use serde::Serialize;
7use serde::Serializer;
8
9use crate::algorithms::convolution::*;
10use crate::algorithms::linsolve::LinSolveRing;
11use crate::algorithms::poly_factor::FactorPolyField;
12use crate::compute_locally::InterpolationBaseRing;
13use crate::divisibility::*;
14use crate::{impl_localpir_wrap_unwrap_homs, impl_localpir_wrap_unwrap_isos, impl_field_wrap_unwrap_homs, impl_field_wrap_unwrap_isos};
15use crate::integer::*;
16use crate::iters::multi_cartesian_product;
17use crate::iters::MultiProduct;
18use crate::matrix::OwnedMatrix;
19use crate::primitive_int::StaticRing;
20use crate::rings::field::{AsField, AsFieldBase};
21use crate::rings::finite::*;
22use crate::rings::poly::dense_poly::DensePolyRing;
23use crate::seq::*;
24use crate::ring::*;
25use crate::integer::IntegerRingStore;
26use crate::rings::extension::create_multiplication_matrix;
27use crate::delegate::DelegateRing;
28use crate::homomorphism::*;
29use crate::serialization::*;
30use crate::seq::sparse::SparseMapVector;
31
32use super::FreeAlgebra;
33use super::FreeAlgebraStore;
34
35///
36/// Implementation for rings that are generated by a single algebraic element over a base ring,
37/// equivalently a quotient of a univariate polynomial ring `R[X]/(f(X))`.
38/// 
39/// # Example
40/// ```
41/// # use feanor_math::ring::*;
42/// # use feanor_math::rings::extension::*;
43/// # use feanor_math::primitive_int::*;
44/// # use feanor_math::rings::extension::extension_impl::*;
45/// # use feanor_math::assert_el_eq;
46/// let base_ring = StaticRing::<i64>::RING;
47/// // ring of integers in the 6th cyclotomic number field
48/// let ring = FreeAlgebraImpl::new(base_ring, 2, [-1, 1]);
49/// let root_of_unity = ring.canonical_gen();
50/// assert_el_eq!(ring, ring.one(), ring.pow(root_of_unity, 6));
51/// ```
52/// 
53pub struct FreeAlgebraImplBase<R, V, A = Global, C = KaratsubaAlgorithm>
54    where R: RingStore, 
55        V: VectorView<El<R>>, 
56        A: Allocator + Clone,
57        C: ConvolutionAlgorithm<R::Type>
58{
59    base_ring: R,
60    x_pow_rank: V,
61    element_allocator: A,
62    log2_padded_len: usize,
63    rank: usize,
64    gen_name: &'static str,
65    convolution: C
66}
67
68/// 
69/// Implementation for rings that are generated by a single algebraic element over a base ring,
70/// equivalently a quotient of a univariate polynomial ring `R[X]/(f(X))`. For details, see
71/// [`FreeAlgebraImplBase`].
72/// 
73pub type FreeAlgebraImpl<R, V, A = Global, C = KaratsubaAlgorithm> = RingValue<FreeAlgebraImplBase<R, V, A, C>>;
74
75impl<R, V> FreeAlgebraImpl<R, V>
76    where R: RingStore, V: VectorView<El<R>>
77{
78    ///
79    /// Creates a new [`FreeAlgebraImpl`] ring as extension of the given base ring.
80    /// 
81    /// The created ring is `R[X]/(X^rank - sum_i x_pow_rank[i] X^i)`.
82    /// 
83    pub fn new(base_ring: R, rank: usize, x_pow_rank: V) -> Self {
84        Self::new_with(base_ring, rank, x_pow_rank, "θ", Global, STANDARD_CONVOLUTION)
85    }
86}
87
88impl<R, V, A, C> Clone for FreeAlgebraImplBase<R, V, A, C>
89    where R: RingStore + Clone, 
90        V: VectorView<El<R>> + Clone,
91        A: Allocator + Clone,
92        C: ConvolutionAlgorithm<R::Type> + Clone
93{
94    fn clone(&self) -> Self {
95        Self {
96            base_ring: self.base_ring.clone(),
97            x_pow_rank: self.x_pow_rank.clone(),
98            element_allocator: self.element_allocator.clone(),
99            log2_padded_len: self.log2_padded_len,
100            rank: self.rank,
101            convolution: self.convolution.clone(),
102            gen_name: self.gen_name
103        }
104    }
105}
106
107impl<R, V, A, C> Copy for FreeAlgebraImplBase<R, V, A, C>
108    where R: RingStore + Copy, 
109        V: VectorView<El<R>> + Copy,
110        A: Allocator + Copy,
111        C: ConvolutionAlgorithm<R::Type> + Copy,
112        El<R>: Copy
113{}
114
115pub struct FreeAlgebraImplEl<R, A = Global>
116    where R: RingStore, A: Allocator
117{
118    values: Box<[El<R>], A>
119}
120
121impl<R, V, A, C> FreeAlgebraImpl<R, V, A, C>
122    where R: RingStore, 
123        V: VectorView<El<R>>,
124        A: Allocator + Clone,
125        C: ConvolutionAlgorithm<R::Type>
126{
127    #[stability::unstable(feature = "enable")]
128    pub fn new_with(base_ring: R, rank: usize, x_pow_rank: V, gen_name: &'static str, element_allocator: A, convolution: C) -> Self {
129        assert!(rank >= 1);
130        assert!(x_pow_rank.len() <= rank);
131        let log2_padded_len = StaticRing::<i64>::RING.abs_log2_ceil(&(rank as i64)).unwrap();
132        RingValue::from(FreeAlgebraImplBase {
133            base_ring, gen_name, x_pow_rank, element_allocator, rank, log2_padded_len, convolution
134        })
135    }
136}
137
138impl<R, V, A, C> FreeAlgebraImplBase<R, V, A, C>
139    where R: RingStore, 
140        V: VectorView<El<R>>,
141        A: Allocator + Clone,
142        C: ConvolutionAlgorithm<R::Type>
143{
144    #[stability::unstable(feature = "enable")]
145    pub fn set_convolution<C_new: ConvolutionAlgorithm<R::Type>>(self, new_convolution: C_new) -> FreeAlgebraImpl<R, V, A, C_new> {
146        RingValue::from(FreeAlgebraImplBase {
147            base_ring: self.base_ring,
148            x_pow_rank: self.x_pow_rank,
149            element_allocator: self.element_allocator,
150            log2_padded_len: self.log2_padded_len,
151            rank: self.rank,
152            convolution: new_convolution,
153            gen_name: self.gen_name
154        })
155    }
156
157    #[stability::unstable(feature = "enable")]
158    pub fn allocator(&self) -> &A {
159        &self.element_allocator
160    }
161
162    #[stability::unstable(feature = "enable")]
163    pub fn gen_name(&self) -> &'static str {
164        self.gen_name
165    }
166
167    #[stability::unstable(feature = "enable")]
168    pub fn x_pow_rank(&self) -> &V {
169        &self.x_pow_rank
170    }
171
172    #[stability::unstable(feature = "enable")]
173    pub fn convolution(&self) -> &C {
174        &self.convolution
175    }
176
177    fn reduce_mod_poly(&self, data: &mut [El<R>]) {
178        struct ReduceModulo<'a, R>
179            where R: RingStore
180        {
181            rank: usize,
182            base_ring: &'a R,
183            data: &'a mut [El<R>]
184        }
185
186        impl<'a, R> SparseVectorViewOperation<El<R>> for ReduceModulo<'a, R>
187            where R: RingStore
188        {
189            type Output<'b> = ()
190                where Self: 'b;
191        
192            fn execute<'b, V: 'b + VectorViewSparse<El<R>>>(self, vector: V) -> () {
193                for i in (self.rank..(2 * self.rank)).rev() {
194                    for (j, c) in vector.nontrivial_entries() {
195                        let add = self.base_ring.mul_ref(c, &mut self.data[i]);
196                        self.base_ring.add_assign(&mut self.data[i - self.rank + j], add);
197                    }
198                }
199            }
200        }
201
202        let was_sparse = self.x_pow_rank.specialize_sparse(ReduceModulo {
203            rank: self.rank,
204            base_ring: self.base_ring(),
205            data: data
206        });
207        if was_sparse.is_err() {
208            for i in (self.rank()..(2 * self.rank())).rev() {
209                for j in 0..self.x_pow_rank.len() {
210                    let add = self.base_ring.mul_ref(self.x_pow_rank.at(j), &data[i]);
211                    self.base_ring.add_assign(&mut data[i - self.rank() + j], add);
212                }
213            }
214        }
215    }
216}
217
218impl<R, V, A, C> PartialEq for FreeAlgebraImplBase<R, V, A, C>
219    where R: RingStore, 
220        V: VectorView<El<R>>,
221        A: Allocator + Clone,
222        C: ConvolutionAlgorithm<R::Type>
223{
224    fn eq(&self, other: &Self) -> bool {
225        self.base_ring().get_ring() == other.base_ring().get_ring() && self.rank() == other.rank() &&
226            (0..self.rank()).all(|i| (i >= self.x_pow_rank.len() && i >= other.x_pow_rank.len()) ||
227                (i >= self.x_pow_rank.len() && self.base_ring().is_zero(other.x_pow_rank.at(i))) ||
228                (i >= other.x_pow_rank.len() && self.base_ring().is_zero(self.x_pow_rank.at(i))) ||
229                self.base_ring().eq_el(self.x_pow_rank.at(i), other.x_pow_rank.at(i)))
230    }
231}
232
233impl<R, V, A, C> RingBase for FreeAlgebraImplBase<R, V, A, C>
234    where R: RingStore, 
235        V: VectorView<El<R>>,
236        A: Allocator + Clone,
237        C: ConvolutionAlgorithm<R::Type>
238{
239    type Element = FreeAlgebraImplEl<R, A>;
240    
241    fn clone_el(&self, val: &Self::Element) -> Self::Element {
242        debug_assert_eq!(1 << self.log2_padded_len, val.values.len());
243        let mut result_values = Vec::with_capacity_in(val.values.len(), self.element_allocator.clone());
244        result_values.extend(val.values.iter().map(|x| self.base_ring().clone_el(x)));
245        return FreeAlgebraImplEl {
246            values: result_values.into_boxed_slice()
247        };
248    }
249
250    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
251        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
252        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
253        for i in 0..self.rank() {
254            self.base_ring().add_assign_ref(&mut lhs.values[i], &rhs.values[i]);
255        }
256    }
257
258    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
259        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
260        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
261        for (i, x) in (0..self.rank()).zip(rhs.values.iter()) {
262            self.base_ring().add_assign_ref(&mut lhs.values[i], x);
263        }
264    }
265
266    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
267        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
268        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
269        for i in 0..self.rank() {
270            self.base_ring().sub_assign_ref(&mut lhs.values[i], &rhs.values[i]);
271        }
272    }
273
274    fn negate_inplace(&self, lhs: &mut Self::Element) {
275        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
276        for i in 0..self.rank() {
277            self.base_ring().negate_inplace(&mut lhs.values[i]);
278        }
279    }
280
281    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
282        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
283        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
284        self.mul_assign_ref(lhs, &rhs)
285    }
286
287    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
288        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
289        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
290        let mut tmp = Vec::with_capacity_in(2 << self.log2_padded_len, self.element_allocator.clone());
291        tmp.resize_with(2 << self.log2_padded_len, || self.base_ring.zero());
292        self.convolution.compute_convolution(&lhs.values[..], &rhs.values[..], &mut tmp[..], self.base_ring());
293        self.reduce_mod_poly(&mut tmp);
294        for i in 0..self.rank() {
295            lhs.values[i] = std::mem::replace(&mut tmp[i], self.base_ring.zero());
296        }
297    }
298    
299    fn from_int(&self, value: i32) -> Self::Element {
300        self.from(self.base_ring().int_hom().map(value))
301    }
302
303    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
304        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
305        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
306        (0..self.rank()).all(|i| self.base_ring().eq_el(&lhs.values[i], &rhs.values[i]))
307    }
308
309    fn is_zero(&self, value: &Self::Element) -> bool {
310        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
311        (0..self.rank()).all(|i| self.base_ring.is_zero(&value.values[i]))
312    }
313
314    fn is_one(&self, value: &Self::Element) -> bool {
315        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
316        self.base_ring().is_one(&value.values[0]) && (1..self.rank()).all(|i| self.base_ring.is_zero(&value.values[i]))
317    }
318
319    fn is_neg_one(&self, value: &Self::Element) -> bool {
320        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
321        self.base_ring().is_neg_one(&value.values[0]) && (1..self.rank()).all(|i| self.base_ring.is_zero(&value.values[i]))
322    }
323
324    fn is_commutative(&self) -> bool {
325        self.base_ring().is_commutative()
326    }
327
328    fn is_noetherian(&self) -> bool {
329        self.base_ring().is_noetherian()
330    }
331
332    fn is_approximate(&self) -> bool {
333        self.base_ring().get_ring().is_approximate()
334    }
335
336    fn dbg<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
337        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
338        self.dbg_within(value, out, EnvBindingStrength::Weakest)
339    }
340
341    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, env: EnvBindingStrength) -> std::fmt::Result {
342        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
343        let poly_ring = DensePolyRing::new(self.base_ring(), self.gen_name);
344        poly_ring.get_ring().dbg_within(&RingRef::new(self).poly_repr(&poly_ring, value, &self.base_ring().identity()), out, env)
345    }
346
347    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) {
348        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
349        for i in 0..self.rank() {
350            self.base_ring().int_hom().mul_assign_map(&mut lhs.values[i], rhs);
351        }
352    }
353
354    fn characteristic<I: IntegerRingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
355        where I::Type: IntegerRing
356    {
357        self.base_ring().characteristic(ZZ)
358    }
359
360    fn square(&self, value: &mut Self::Element) {
361        struct SquareIfPreparable<'a, R, V, A, C>
362            where R: RingStore, 
363                V: VectorView<El<R>>,
364                A: Allocator + Clone,
365                C: ConvolutionAlgorithm<R::Type>
366        {
367            x: El<FreeAlgebraImpl<R, V, A, C>>,
368            ring: &'a FreeAlgebraImplBase<R, V, A, C>
369        }
370        impl<'a, R, V, A, C> PreparedConvolutionOperation<C, R::Type> for SquareIfPreparable<'a, R, V, A, C>
371            where R: RingStore, 
372                V: VectorView<El<R>>,
373                A: Allocator + Clone,
374                C: ConvolutionAlgorithm<R::Type>
375        {
376            type Output = El<FreeAlgebraImpl<R, V, A, C>>;
377
378            fn execute(mut self) -> Self::Output
379                where C:PreparedConvolutionAlgorithm<R::Type>
380            {
381                let mut tmp = Vec::with_capacity_in(2 << self.ring.log2_padded_len, self.ring.element_allocator.clone());
382                tmp.resize_with(2 << self.ring.log2_padded_len, || self.ring.base_ring().zero());
383                let x_prepared = self.ring.convolution.prepare_convolution_operand(&self.x.values[..], self.ring.base_ring());
384                self.ring.convolution.compute_convolution_prepared(&x_prepared, &x_prepared, &mut tmp, self.ring.base_ring());
385                self.ring.reduce_mod_poly(&mut tmp);
386                for i in 0..self.ring.rank() {
387                    self.x.values[i] = std::mem::replace(&mut tmp[i], self.ring.base_ring().zero());
388                }
389                return self.x;
390            }
391        }
392        match <C as ConvolutionAlgorithm<R::Type>>::specialize_prepared_convolution(SquareIfPreparable {
393            x: std::mem::replace(value, FreeAlgebraImplEl { values: Vec::new_in(self.element_allocator.clone()).into_boxed_slice() }),
394            ring: self
395        }) {
396            Ok(result) => *value = result,
397            Err(function) => *value = self.mul_ref(&function.x, &function.x)
398        }
399    }
400}
401
402impl<R, V, A, C> RingExtension for FreeAlgebraImplBase<R, V, A, C>
403    where R: RingStore, 
404        V: VectorView<El<R>>,
405        A: Allocator + Clone,
406        C: ConvolutionAlgorithm<R::Type>
407{
408    type BaseRing = R;
409    
410    fn base_ring<'a>(&'a self) -> &'a Self::BaseRing {
411        &self.base_ring
412    }
413
414    fn from(&self, x: El<Self::BaseRing>) -> Self::Element {
415        let mut result_values = Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone());
416        result_values.push(x);
417        result_values.extend((0..((1 << self.log2_padded_len) - 1)).map(|_| self.base_ring().zero()));
418        return FreeAlgebraImplEl {
419            values: result_values.into_boxed_slice()
420        };
421    }
422
423    fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
424        for i in 0..self.rank() {
425            self.base_ring().mul_assign_ref(&mut lhs.values[i], rhs);
426        }
427    }
428}
429
430///
431/// It seems like a good idea to also implement [`DivisibilityRing::prepare_divisor()`]
432/// and the prepared division functions here. However, currently the interface of
433/// [`LinSolveRing`] does not support this. I am not yet sure what is the best approach
434/// here, but it seems unlikely that this can be done properly without a breaking release
435///  - Either change [`LinSolveRing`] to support "factorizations" of matrices, or rather
436///    the equivalent to "prepared divisors" of matrices
437///  - Implement [`DivisibilityRing::prepare_divisor()`] only for `R::Type: [`PrincipalIdealRing`]`,
438///    which however requires specialization or a specialization workaround
439/// 
440/// TODO: Decide and implement on the next breaking release
441/// 
442impl<R, V, A, C> DivisibilityRing for FreeAlgebraImplBase<R, V, A, C>
443    where R: RingStore, 
444        R::Type: LinSolveRing,
445        V: VectorView<El<R>>,
446        A: Allocator + Clone,
447        C: ConvolutionAlgorithm<R::Type>
448{
449    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
450        let mut mul_matrix: OwnedMatrix<_> = create_multiplication_matrix(RingRef::new(self), rhs);
451        let mut lhs_matrix: OwnedMatrix<_> = OwnedMatrix::zero(self.rank(), 1, self.base_ring());
452        let data = self.wrt_canonical_basis(&lhs);
453        for j in 0..self.rank() {
454            *lhs_matrix.at_mut(j, 0) = data.at(j);
455        }
456        let mut solution: OwnedMatrix<_> = OwnedMatrix::zero(self.rank(), 1, self.base_ring());
457        let has_sol = self.base_ring().get_ring().solve_right(mul_matrix.data_mut(), lhs_matrix.data_mut(), solution.data_mut(), Global);
458        if has_sol.is_solved() {
459            return Some(self.from_canonical_basis((0..self.rank()).map(|i| self.base_ring().clone_el(solution.at(i, 0)))));
460        } else {
461            return None;
462        }
463    }
464
465    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
466        where I: Iterator<Item = &'a Self::Element>, 
467            Self: 'a
468    {
469        self.base_ring().get_ring().balance_factor(elements.flat_map(|x| x.values.iter())).map(|c| RingRef::new(self).inclusion().map(c))
470    }
471
472    default fn invert(&self, el: &Self::Element) -> Option<Self::Element> {
473        self.checked_left_div(&self.one(), el)
474    }
475}
476
477impl<R, V, A, C> SerializableElementRing for FreeAlgebraImplBase<R, V, A, C>
478    where R: RingStore, 
479        V: VectorView<El<R>>,
480        A: Allocator + Clone,
481        C: ConvolutionAlgorithm<R::Type>,
482        R::Type: SerializableElementRing
483{
484    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
485        where D: Deserializer<'de>
486    {
487        DeserializeSeedNewtype::new("ExtensionRingEl", DeserializeSeedSeq::new(
488            std::iter::repeat(DeserializeWithRing::new(self.base_ring())).take(self.rank()),
489            Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone()),
490            |mut current, next| { current.push(next); current }
491        )).deserialize(deserializer).map(|mut values| {
492            values.resize_with(1 << self.log2_padded_len, || self.base_ring().zero());
493            FreeAlgebraImplEl { values: values.into_boxed_slice() }
494        })
495    }
496
497    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
498        where S: Serializer
499    {
500        debug_assert_eq!(1 << self.log2_padded_len, el.values.len());
501        SerializableNewtype::new("ExtensionRingEl", SerializableSeq::new(
502            (0..self.rank()).map_fn(|i| SerializeWithRing::new(&el.values[i], self.base_ring()))
503        )).serialize(serializer)
504    }
505}
506
507impl<R, V, A, C> FreeAlgebra for FreeAlgebraImplBase<R, V, A, C>
508    where R: RingStore, 
509        V: VectorView<El<R>>,
510        A: Allocator + Clone,
511        C: ConvolutionAlgorithm<R::Type>
512{
513    type VectorRepresentation<'a> = CloneElFn<&'a [El<R>], El<R>, CloneRingEl<&'a R>>
514        where Self: 'a;
515
516    fn canonical_gen(&self) -> Self::Element {
517        if self.rank() == 1 {
518            if self.x_pow_rank.len() == 1 {
519                self.from_canonical_basis([self.base_ring.clone_el(self.x_pow_rank.at(0))])
520            } else {
521                assert!(self.x_pow_rank.len() == 0);
522                self.zero()
523            }
524        } else {
525            self.from_canonical_basis((0..self.rank()).map(|i| if i == 1 { self.base_ring.one() } else { self.base_ring.zero() }))
526        }
527    }
528
529    fn wrt_canonical_basis<'a>(&'a self, el: &'a Self::Element) -> Self::VectorRepresentation<'a> {
530        (&el.values[..self.rank]).clone_ring_els(self.base_ring())
531    }
532
533    fn from_canonical_basis<W>(&self, vec: W) -> Self::Element
534        where W: IntoIterator<Item = El<Self::BaseRing>>,
535            W::IntoIter: DoubleEndedIterator
536    {
537        let mut given_len = 0;
538        let mut vec_it = vec.into_iter().inspect(|_| given_len += 1);
539        let mut result = Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone());
540        result.extend(vec_it.by_ref());
541        result.extend((0..((1 << self.log2_padded_len) - self.rank())).map(|_| self.base_ring().zero()));
542        assert!(vec_it.next().is_none());
543        assert_eq!(given_len, self.rank());
544        FreeAlgebraImplEl { values: result.into_boxed_slice() }
545    }
546
547    fn rank(&self) -> usize {
548        self.rank
549    }
550}
551
552impl<R, V, A, C> InterpolationBaseRing for AsFieldBase<FreeAlgebraImpl<R, V, A, C>>
553    where R: RingStore + Clone, 
554        R::Type: LinSolveRing + FactorPolyField,
555        V: VectorView<El<R>>,
556        A: Allocator + Clone,
557        C: ConvolutionAlgorithm<R::Type>
558{
559    type ExtendedRingBase<'a> = AsFieldBase<FreeAlgebraImpl<RingRef<'a, Self>, SparseMapVector<RingRef<'a, Self>>, A, KaratsubaAlgorithm<Global>>>
560        where Self: 'a;
561
562    type ExtendedRing<'a> = AsField<FreeAlgebraImpl<RingRef<'a, Self>, SparseMapVector<RingRef<'a, Self>>, A, KaratsubaAlgorithm<Global>>>
563        where Self: 'a;
564
565    fn in_base<'a, S>(&self, ext_ring: S, el: El<S>) -> Option<Self::Element>
566        where Self: 'a, S: RingStore<Type = Self::ExtendedRingBase<'a>>
567    {
568        let wrt_basis = ext_ring.wrt_canonical_basis(&el);
569        if wrt_basis.iter().skip(1).all(|x| self.is_zero(&x)) {
570            return Some(wrt_basis.at(0));
571        } else {
572            return None;
573        }
574    }
575
576    fn in_extension<'a, S>(&self, ext_ring: S, el: Self::Element) -> El<S>
577        where Self: 'a, S: RingStore<Type = Self::ExtendedRingBase<'a>>
578    {
579        ext_ring.inclusion().map(el)
580    }
581
582    fn interpolation_points<'a>(&'a self, count: usize) -> (Self::ExtendedRing<'a>, Vec<El<Self::ExtendedRing<'a>>>) {
583        let ZZbig = BigIntRing::RING;
584        let characteristic = self.base_ring().characteristic(&ZZbig).unwrap();
585        if ZZbig.is_zero(&characteristic) {
586            let mut modulus = SparseMapVector::new(1, RingRef::new(self));
587            *modulus.at_mut(0) = self.one();
588            let field = AsField::from(AsFieldBase::promise_is_perfect_field(FreeAlgebraImpl::new_with(RingRef::new(self), 1, modulus, "X", self.get_delegate().element_allocator.clone(), STANDARD_CONVOLUTION)));
589            let points = (0..count).map(|n| field.int_hom().map(n as i32)).collect();
590            return (field, points);
591        } else {
592            unimplemented!()
593        }
594    }
595}
596
597pub struct WRTCanonicalBasisElementCreator<'a, R, V, A, C>
598    where R: RingStore, 
599        R::Type: FiniteRing, 
600        V: VectorView<El<R>>,
601        A: Allocator + Clone,
602        C: ConvolutionAlgorithm<R::Type>
603{
604    base_ring: &'a FreeAlgebraImplBase<R, V, A, C>
605}
606
607impl<'a, R, V, A, C> Clone for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
608    where R: RingStore, 
609        R::Type: FiniteRing, 
610        V: VectorView<El<R>>,
611        A: Allocator + Clone,
612        C: ConvolutionAlgorithm<R::Type>
613{
614    fn clone(&self) -> Self { *self }
615}
616
617impl<'a, 'b, R, V, A, C> FnOnce<(&'b [El<R>], )> for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
618    where R: RingStore, 
619        R::Type: FiniteRing, 
620        V: VectorView<El<R>>,
621        A: Allocator + Clone,
622        C: ConvolutionAlgorithm<R::Type>
623{
624    type Output = El<FreeAlgebraImpl<R, V, A, C>>;
625
626    extern "rust-call" fn call_once(mut self, args: (&'b [El<R>], )) -> Self::Output {
627        self.call_mut(args)
628    }
629}
630
631impl<'a, 'b, R, V, A, C> FnMut<(&'b [El<R>], )> for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
632    where R: RingStore, 
633        R::Type: FiniteRing, 
634        V: VectorView<El<R>>,
635        A: Allocator + Clone,
636        C: ConvolutionAlgorithm<R::Type>
637{
638    extern "rust-call" fn call_mut(&mut self, args: (&'b [El<R>], )) -> Self::Output {
639        self.base_ring.from_canonical_basis(args.0.iter().map(|x| self.base_ring.base_ring().clone_el(x)))
640    }
641}
642
643impl<'a, R, V, A, C> Copy for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
644    where R: RingStore, 
645        R::Type: FiniteRing, 
646        V: VectorView<El<R>>,
647        A: Allocator + Clone,
648        C: ConvolutionAlgorithm<R::Type>
649{}
650
651impl<R, V, A, C> FiniteRing for FreeAlgebraImplBase<R, V, A, C>
652    where R: RingStore, 
653        R::Type: FiniteRing, 
654        V: VectorView<El<R>>,
655        A: Allocator + Clone,
656        C: ConvolutionAlgorithm<R::Type>
657{
658    type ElementsIter<'a> = MultiProduct<<R::Type as FiniteRing>::ElementsIter<'a>, WRTCanonicalBasisElementCreator<'a, R, V, A, C>, CloneRingEl<&'a R>, Self::Element>
659        where Self: 'a;
660
661    fn elements<'a>(&'a self) -> Self::ElementsIter<'a> {
662        multi_cartesian_product((0..self.rank()).map(|_| self.base_ring().elements()), WRTCanonicalBasisElementCreator { base_ring: self }, CloneRingEl(self.base_ring()))
663    }
664
665    fn size<I: IntegerRingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
666        where I::Type: IntegerRing
667    {
668        let base_ring_size = self.base_ring().size(ZZ)?;
669        if ZZ.get_ring().representable_bits().is_none() || ZZ.abs_log2_ceil(&base_ring_size).unwrap() * self.rank() < ZZ.get_ring().representable_bits().unwrap() {
670            Some(ZZ.pow(base_ring_size, self.rank()))
671        } else {
672            None
673        }
674    }
675
676    fn random_element<G: FnMut() -> u64>(&self, mut rng: G) -> <Self as RingBase>::Element {
677        self.from_canonical_basis((0..self.rank()).map(|_| self.base_ring().random_element(&mut rng)))
678    }
679}
680
681impl_field_wrap_unwrap_homs!{
682    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
683        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
684            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
685            R2::Type: CanHomFrom<R1::Type>
686}
687
688impl_field_wrap_unwrap_isos!{
689    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
690        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
691            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
692            R2::Type: CanIsoFromTo<R1::Type>
693}
694
695impl_localpir_wrap_unwrap_homs!{
696    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
697        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
698            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
699            R2::Type: CanHomFrom<R1::Type>
700}
701
702impl_localpir_wrap_unwrap_isos!{
703    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
704        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
705            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
706            R2::Type: CanIsoFromTo<R1::Type>
707}
708
709impl<R1, V1, A1, C1, R2, V2, A2, C2> CanHomFrom<FreeAlgebraImplBase<R1, V1, A1, C1>> for FreeAlgebraImplBase<R2, V2, A2, C2>
710    where R1: RingStore, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
711        R2: RingStore, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
712        R2::Type: CanHomFrom<R1::Type>
713{
714    type Homomorphism = <R2::Type as CanHomFrom<R1::Type>>::Homomorphism;
715
716    fn has_canonical_hom(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>) -> Option<Self::Homomorphism> {
717        if self.rank() == from.rank() {
718            let hom = self.base_ring.get_ring().has_canonical_hom(from.base_ring.get_ring())?;
719            if (0..self.rank()).all(|i| (i >= self.x_pow_rank.len() && i >= from.x_pow_rank.len()) ||
720                (i >= self.x_pow_rank.len() && from.base_ring().is_zero(from.x_pow_rank.at(i))) ||
721                (i >= from.x_pow_rank.len() && self.base_ring().is_zero(self.x_pow_rank.at(i))) ||
722                self.base_ring.eq_el(self.x_pow_rank.at(i), &self.base_ring.get_ring().map_in_ref(from.base_ring.get_ring(), from.x_pow_rank.at(i), &hom))
723            ) {
724                Some(hom)
725            } else {
726                None
727            }
728        } else {
729            None
730        }
731    }
732
733    fn map_in(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>, el: <FreeAlgebraImplBase<R1, V1, A1> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
734        self.from_canonical_basis((0..self.rank()).map(|i| self.base_ring.get_ring().map_in_ref(from.base_ring.get_ring(), &el.values[i], hom)))
735    }
736}
737
738impl<R1, V1, A1, C1, R2, V2, A2, C2> CanIsoFromTo<FreeAlgebraImplBase<R1, V1, A1, C1>> for FreeAlgebraImplBase<R2, V2, A2, C2>
739    where R1: RingStore, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
740        R2: RingStore, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
741        R2::Type: CanIsoFromTo<R1::Type>
742{
743    type Isomorphism = <R2::Type as CanIsoFromTo<R1::Type>>::Isomorphism;
744
745    fn has_canonical_iso(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>) -> Option<Self::Isomorphism> {
746        if self.rank() == from.rank() {
747            let iso = self.base_ring.get_ring().has_canonical_iso(from.base_ring.get_ring())?;
748            if (0..self.rank()).all(|i|(i >= self.x_pow_rank.len() && i >= from.x_pow_rank.len()) ||
749                (i >= self.x_pow_rank.len() && from.base_ring().is_zero(from.x_pow_rank.at(i))) ||
750                (i >= from.x_pow_rank.len() && self.base_ring().is_zero(self.x_pow_rank.at(i))) ||
751                from.base_ring.eq_el(&self.base_ring.get_ring().map_out(from.base_ring.get_ring(), self.base_ring.clone_el(self.x_pow_rank.at(i)), &iso), from.x_pow_rank.at(i))
752            ) {
753                Some(iso)
754            } else {
755                None
756            }
757        } else {
758            None
759        }
760    }
761
762    fn map_out(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>, el: <FreeAlgebraImplBase<R2, V2, A2> as RingBase>::Element, iso: &Self::Isomorphism) -> <FreeAlgebraImplBase<R1, V1, A1, C1> as RingBase>::Element {
763        from.from_canonical_basis((0..self.rank()).map(|i| self.base_ring.get_ring().map_out(from.base_ring.get_ring(), self.base_ring.clone_el(&el.values[i]), iso)))
764    }
765}
766
767#[cfg(test)]
768use crate::rings::zn::zn_64::{Zn, ZnEl};
769#[cfg(test)]
770use crate::rings::zn::ZnRingStore;
771#[cfg(test)]
772use crate::rings::zn::zn_static;
773#[cfg(test)]
774use crate::compute_locally::ToExtRingMap;
775#[cfg(test)]
776use crate::rings::rational::RationalField;
777#[cfg(test)]
778use crate::algorithms::convolution::fft::FFTConvolution;
779
780#[cfg(test)]
781fn test_ring0_and_elements() -> (FreeAlgebraImpl<Zn, [ZnEl; 1]>, Vec<FreeAlgebraImplEl<Zn>>) {
782    let R = FreeAlgebraImpl::new(Zn::new(7), 1, [Zn::new(7).neg_one()]);
783    let elements = R.elements().collect();
784    return (R, elements);
785}
786
787#[cfg(test)]
788fn test_ring1_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, [i64; 2]>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
789    let ZZ = StaticRing::<i64>::RING;
790    let R = FreeAlgebraImpl::new(ZZ, 2, [1, 1]);
791    let mut elements = Vec::new();
792    for a in -3..=3 {
793        for b in -3..=3 {
794            elements.push(R.from_canonical_basis([a, b]));
795        }
796    }
797    return (R, elements);
798}
799
800#[cfg(test)]
801fn test_ring2_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, [i64; 3]>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
802    let ZZ = StaticRing::<i64>::RING;
803    let R = FreeAlgebraImpl::new(ZZ, 3, [1, -1, 1]);
804    let mut elements = Vec::new();
805    for a in [-2, 0, 1, 2] {
806        for b in [-2, 0, 2] {
807            for c in [-2, 0, 2] {
808                elements.push(R.from_canonical_basis([a, b, c]));
809            }
810        }
811    }
812    return (R, elements);
813}
814
815#[cfg(test)]
816fn test_ring3_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, [i64; 1]>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
817    let ZZ = StaticRing::<i64>::RING;
818    let R = FreeAlgebraImpl::new(ZZ, 3, [1]);
819    let mut elements = Vec::new();
820    for a in [-2, 0, 1, 2] {
821        for b in [-2, 0, 2] {
822            for c in [-2, 0, 2] {
823                elements.push(R.from_canonical_basis([a, b, c]));
824            }
825        }
826    }
827    return (R, elements);
828}
829
830#[cfg(test)]
831fn test_ring4_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, SparseMapVector<StaticRing<i64>>>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
832    let ZZ = StaticRing::<i64>::RING;
833    // ZZ[X]/(X^3 - X)
834    let mut modulus = SparseMapVector::new(3, StaticRing::<i64>::RING);
835    *modulus.at_mut(1) = 1;
836    let R = FreeAlgebraImpl::new(ZZ, 3, modulus);
837    let mut elements = Vec::new();
838    for a in [-2, 0, 1, 2] {
839        for b in [-2, 0, 2] {
840            for c in [-2, 0, 2] {
841                elements.push(R.from_canonical_basis([a, b, c]));
842            }
843        }
844    }
845    return (R, elements);
846}
847
848#[test]
849fn test_sparse() {
850    let (ring, _) = test_ring4_and_elements();
851    assert_el_eq!(ring, ring.canonical_gen(), ring.pow(ring.canonical_gen(), 3));
852}
853
854#[test]
855fn test_ring_axioms() {
856    let (ring, els) = test_ring0_and_elements();
857    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
858    let (ring, els) = test_ring1_and_elements();
859    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
860    let (ring, els) = test_ring2_and_elements();
861    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
862    let (ring, els) = test_ring3_and_elements();
863    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
864    let (ring, els) = test_ring4_and_elements();
865    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
866    
867    let (ring, els) = test_ring2_and_elements();
868    let ring = ring.into().set_convolution(FFTConvolution::new_with(Global));
869    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
870
871    let base_ring = zn_static::Fp::<257>::RING;
872    let x_pow_rank = vec![base_ring.neg_one(); 64];
873    let ring = FreeAlgebraImpl::new(base_ring, 64, x_pow_rank);
874    let mut rng = oorandom::Rand64::new(0);
875    let els = (0..10).map(|_| ring.from_canonical_basis((0..64).map(|_| ring.base_ring().random_element(|| rng.rand_u64()))));
876    crate::ring::generic_tests::test_ring_axioms(&ring, els);
877}
878
879#[test]
880fn test_rank_1_ring() {
881    let base_ring = Zn::new(5).as_field().ok().unwrap();
882    let ring = FreeAlgebraImpl::new(base_ring, 1, [base_ring.int_hom().map(1)]).as_field().ok().unwrap();
883    crate::field::generic_tests::test_field_axioms(&ring, ring.elements());
884
885    assert_el_eq!(ring, ring.one(), ring.canonical_gen());
886}
887
888#[test]
889fn test_free_algebra_axioms() {
890    let (ring, _) = test_ring0_and_elements();
891    super::generic_tests::test_free_algebra_axioms(ring);
892    let (ring, _) = test_ring1_and_elements();
893    super::generic_tests::test_free_algebra_axioms(ring);
894    let (ring, _) = test_ring2_and_elements();
895    super::generic_tests::test_free_algebra_axioms(ring);
896    let (ring, _) = test_ring3_and_elements();
897    super::generic_tests::test_free_algebra_axioms(ring);
898    let (ring, _) = test_ring4_and_elements();
899    super::generic_tests::test_free_algebra_axioms(ring);
900}
901
902#[test]
903fn test_division() {
904    let base_ring = Zn::new(4);
905    let i = base_ring.int_hom();
906    let ring = FreeAlgebraImpl::new(base_ring, 2, [i.map(-1), i.map(-1)]);
907
908    assert_el_eq!(ring, 
909        &ring.from_canonical_basis([i.map(1), i.map(3)]), 
910        &ring.checked_div(&ring.one(), &ring.from_canonical_basis([i.map(2), i.map(3)])).unwrap()
911    );
912
913    let a = ring.from_canonical_basis([i.map(2), i.map(2)]);
914    let b = ring.from_canonical_basis([i.map(0), i.map(2)]);
915    assert_el_eq!(ring, a, ring.mul(ring.checked_div(&a, &b).unwrap(), b));
916
917    assert!(ring.checked_div(&ring.one(), &a).is_none());
918}
919
920#[test]
921fn test_division_ring_of_integers() {
922    let base_ring = StaticRing::<i64>::RING;
923    let ring = FreeAlgebraImpl::new(base_ring, 2, [11, 0]);
924
925    // the solution to Pell's equation is 10^2 - 3^2 * 11 = 1
926    let u = ring.from_canonical_basis([10, 3]);
927    let u_inv = ring.from_canonical_basis([10, -3]);
928
929    assert_el_eq!(ring, u_inv, ring.checked_div(&ring.one(), &u).unwrap());
930    assert_el_eq!(ring, ring.pow(u_inv, 3), &ring.checked_div(&ring.one(), &ring.pow(u, 3)).unwrap());
931
932    assert!(ring.checked_div(&ring.from_canonical_basis([2, 0]), &ring.from_canonical_basis([3, 0])).is_none());
933}
934
935#[test]
936fn test_divisibility_axioms() {
937    let (ring, els) = test_ring0_and_elements();
938    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
939    let (ring, els) = test_ring1_and_elements();
940    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
941    let (ring, els) = test_ring2_and_elements();
942    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
943    let (ring, els) = test_ring3_and_elements();
944    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
945    let (ring, els) = test_ring4_and_elements();
946    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
947}
948
949#[test]
950fn test_cubic_mul() {
951    let base_ring = zn_static::Zn::<256>::RING;
952    let modulo = base_ring.int_hom();
953    let ring = FreeAlgebraImpl::new(base_ring, 3, [modulo.map(-1), modulo.map(-1), modulo.map(-1)]);
954    let a = ring.from_canonical_basis([modulo.map(0), modulo.map(-1), modulo.map(-1)]);
955    let b = ring.from_canonical_basis([modulo.map(-1), modulo.map(-2), modulo.map(-1)]);
956    assert_el_eq!(ring, b, ring.pow(a, 2));
957}
958
959#[test]
960fn test_as_field() {
961    let base_ring = Zn::new(5).as_field().ok().unwrap();
962    let ring = FreeAlgebraImpl::new(base_ring, 1, [base_ring.int_hom().map(1)]).as_field().ok().unwrap();
963    crate::field::generic_tests::test_field_axioms(&ring, ring.elements());
964
965    let base_ring = Zn::new(3).as_field().ok().unwrap();
966    let ring = FreeAlgebraImpl::new(base_ring, 2, [base_ring.int_hom().map(2)]).as_field().ok().unwrap();
967    crate::field::generic_tests::test_field_axioms(&ring, ring.elements());
968
969    assert!(FreeAlgebraImpl::new(base_ring, 2, [base_ring.int_hom().map(1)]).as_field().is_err());
970}
971
972#[test]
973fn test_serialization() {
974    let (ring, els) = test_ring0_and_elements();
975    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
976    let (ring, els) = test_ring1_and_elements();
977    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
978    let (ring, els) = test_ring2_and_elements();
979    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
980    let (ring, els) = test_ring3_and_elements();
981    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
982    let (ring, els) = test_ring4_and_elements();
983    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
984}
985
986#[test]
987#[should_panic]
988fn test_from_canonical_basis_enforce_len() {
989    let (ring, _) = test_ring1_and_elements();
990    _ = ring.from_canonical_basis([0, 1, 2]);
991}
992
993#[test]
994fn test_interpolation_base_ring() {
995    let base_ring = RationalField::new(StaticRing::<i64>::RING);
996    let ring = FreeAlgebraImpl::new(base_ring, 3, [base_ring.neg_one(), base_ring.neg_one()]).as_field().ok().unwrap();
997    let (ext_map, points) = ToExtRingMap::for_interpolation(ring.get_ring(), 3);
998    for _ in points {
999        assert_el_eq!(&ring, ring.invert(&ring.canonical_gen()).unwrap(), ext_map.as_base_ring_el(ext_map.codomain().invert(&ext_map.map(ring.canonical_gen())).unwrap()));
1000    }
1001}
feanor_math/rings/extension/extension_impl.rs

feanor_math/rings/extension/
extension_impl.rs
