feanor_math/rings/extension/

extension_impl.rs

use std::alloc::{Allocator, Global};
use std::fmt::{Debug, Formatter};
use std::marker::PhantomData;
use std::cell::OnceCell;
use std::mem::replace;

use feanor_serde::dependent_tuple::DeserializeSeedDependentTuple;
use feanor_serde::newtype_struct::DeserializeSeedNewtypeStruct;
use feanor_serde::seq::*;
use feanor_serde::newtype_struct::*;
use serde::de::DeserializeSeed;
use serde::{Deserializer, Serialize, Serializer, Deserialize};

use crate::algorithms::convolution::*;
use crate::algorithms::extension_ops::create_multiplication_matrix;
use crate::algorithms::linsolve::LinSolveRing;
use crate::divisibility::*;
use crate::{impl_localpir_wrap_unwrap_homs, impl_localpir_wrap_unwrap_isos, impl_field_wrap_unwrap_homs, impl_field_wrap_unwrap_isos};
use crate::integer::*;
use crate::iters::multi_cartesian_product;
use crate::iters::MultiProduct;
use crate::rings::poly::PolyRingStore;
use crate::matrix::OwnedMatrix;
use crate::primitive_int::StaticRing;
use crate::rings::finite::*;
use crate::specialization::*;
use crate::rings::poly::dense_poly::DensePolyRing;
use crate::seq::*;
use crate::ring::*;
use crate::integer::IntegerRingStore;
use crate::delegate::DelegateRing;
use crate::homomorphism::*;
use crate::serialization::*;
use crate::seq::sparse::SparseMapVector;

use super::FreeAlgebra;
use super::FreeAlgebraStore;

///
/// Implementation for rings that are generated by a single algebraic element over a base ring,
/// equivalently a quotient of a univariate polynomial ring `R[X]/(f(X))`.
/// 
/// # Example
/// ```rust
/// # use feanor_math::ring::*;
/// # use feanor_math::rings::extension::*;
/// # use feanor_math::primitive_int::*;
/// # use feanor_math::rings::extension::extension_impl::*;
/// # use feanor_math::assert_el_eq;
/// let base_ring = StaticRing::<i64>::RING;
/// // ring of integers in the 6th cyclotomic number field
/// let ring = FreeAlgebraImpl::new(base_ring, 2, [-1, 1]);
/// let root_of_unity = ring.canonical_gen();
/// assert_el_eq!(ring, ring.one(), ring.pow(root_of_unity, 6));
/// ```
/// 
pub struct FreeAlgebraImplBase<R, V, A = Global, C = KaratsubaAlgorithm>
    where R: RingStore, 
        V: VectorView<El<R>>, 
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    base_ring: R,
    x_pow_rank: V,
    element_allocator: A,
    log2_padded_len: usize,
    rank: usize,
    gen_name: &'static str,
    convolution: C
}

/// 
/// Implementation for rings that are generated by a single algebraic element over a base ring,
/// equivalently a quotient of a univariate polynomial ring `R[X]/(f(X))`. For details, see
/// [`FreeAlgebraImplBase`].
/// 
pub type FreeAlgebraImpl<R, V, A = Global, C = KaratsubaAlgorithm> = RingValue<FreeAlgebraImplBase<R, V, A, C>>;

impl<R, V> FreeAlgebraImpl<R, V>
    where R: RingStore, V: VectorView<El<R>>
{
    ///
    /// Creates a new [`FreeAlgebraImpl`] ring as extension of the given base ring.
    /// 
    /// The created ring is `R[X]/(X^rank - sum_i x_pow_rank[i] X^i)`.
    /// 
    pub fn new(base_ring: R, rank: usize, x_pow_rank: V) -> Self {
        Self::new_with_convolution(base_ring, rank, x_pow_rank, "θ", Global, STANDARD_CONVOLUTION)
    }
}

impl<R, V, A, C> Clone for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore + Clone, 
        V: VectorView<El<R>> + Clone,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type> + Clone
{
    fn clone(&self) -> Self {
        Self {
            base_ring: self.base_ring.clone(),
            x_pow_rank: self.x_pow_rank.clone(),
            element_allocator: self.element_allocator.clone(),
            log2_padded_len: self.log2_padded_len,
            rank: self.rank,
            convolution: self.convolution.clone(),
            gen_name: self.gen_name
        }
    }
}

impl<R, V, A, C> Copy for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore + Copy, 
        V: VectorView<El<R>> + Copy,
        A: Allocator + Copy,
        C: ConvolutionAlgorithm<R::Type> + Copy,
        El<R>: Copy
{}

///
/// Type of an element of [`FreeAlgebraImpl`].
/// 
pub struct FreeAlgebraImplEl<R, A = Global>
    where R: RingStore, A: Allocator
{
    values: Box<[El<R>], A>
}

impl<R, A> Debug for FreeAlgebraImplEl<R, A>
    where R: RingStore, A: Allocator,
        El<R>: Debug
{
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", &self.values)
    }
}

impl<R, V, A, C> FreeAlgebraImpl<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    #[stability::unstable(feature = "enable")]
    pub fn new_with_convolution(base_ring: R, rank: usize, x_pow_rank: V, gen_name: &'static str, element_allocator: A, convolution: C) -> Self {
        assert!(rank >= 1);
        assert!(x_pow_rank.len() <= rank);
        let log2_padded_len = StaticRing::<i64>::RING.abs_log2_ceil(&rank.try_into().unwrap()).unwrap();
        RingValue::from(FreeAlgebraImplBase {
            base_ring, gen_name, x_pow_rank, element_allocator, rank, log2_padded_len, convolution
        })
    }
}

impl<R, V, A, C> FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    #[stability::unstable(feature = "enable")]
    pub fn set_convolution<C_new: ConvolutionAlgorithm<R::Type>>(self, new_convolution: C_new) -> FreeAlgebraImpl<R, V, A, C_new> {
        RingValue::from(FreeAlgebraImplBase {
            base_ring: self.base_ring,
            x_pow_rank: self.x_pow_rank,
            element_allocator: self.element_allocator,
            log2_padded_len: self.log2_padded_len,
            rank: self.rank,
            convolution: new_convolution,
            gen_name: self.gen_name
        })
    }

    #[stability::unstable(feature = "enable")]
    pub fn allocator(&self) -> &A {
        &self.element_allocator
    }

    #[stability::unstable(feature = "enable")]
    pub fn gen_name(&self) -> &'static str {
        self.gen_name
    }

    #[stability::unstable(feature = "enable")]
    pub fn x_pow_rank(&self) -> &V {
        &self.x_pow_rank
    }

    #[stability::unstable(feature = "enable")]
    pub fn convolution(&self) -> &C {
        &self.convolution
    }

    fn reduce_mod_poly(&self, data: &mut [El<R>]) {
        struct ReduceModulo<'a, R>
            where R: RingStore
        {
            rank: usize,
            base_ring: &'a R,
            data: &'a mut [El<R>]
        }

        impl<'a, R> SparseVectorViewOperation<El<R>> for ReduceModulo<'a, R>
            where R: RingStore
        {
            type Output<'b> = ()
                where Self: 'b;
        
            fn execute<'b, V: 'b + VectorViewSparse<El<R>>>(self, vector: V) -> () {
                for i in (self.rank..(2 * self.rank)).rev() {
                    for (j, c) in vector.nontrivial_entries() {
                        let add = self.base_ring.mul_ref(c, &mut self.data[i]);
                        self.base_ring.add_assign(&mut self.data[i - self.rank + j], add);
                    }
                }
            }
        }

        let was_sparse = self.x_pow_rank.specialize_sparse(ReduceModulo {
            rank: self.rank,
            base_ring: self.base_ring(),
            data: data
        });
        if was_sparse.is_err() {
            for i in (self.rank()..(2 * self.rank())).rev() {
                for j in 0..self.x_pow_rank.len() {
                    let add = self.base_ring.mul_ref(self.x_pow_rank.at(j), &data[i]);
                    self.base_ring.add_assign(&mut data[i - self.rank() + j], add);
                }
            }
        }
    }
}

impl<R, V, A, C> PartialEq for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    fn eq(&self, other: &Self) -> bool {
        self.base_ring().get_ring() == other.base_ring().get_ring() && self.rank() == other.rank() &&
            (0..self.rank()).all(|i| (i >= self.x_pow_rank.len() && i >= other.x_pow_rank.len()) ||
                (i >= self.x_pow_rank.len() && self.base_ring().is_zero(other.x_pow_rank.at(i))) ||
                (i >= other.x_pow_rank.len() && self.base_ring().is_zero(self.x_pow_rank.at(i))) ||
                self.base_ring().eq_el(self.x_pow_rank.at(i), other.x_pow_rank.at(i)))
    }
}

impl<R, V, A, C> RingBase for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    type Element = FreeAlgebraImplEl<R, A>;
    
    fn clone_el(&self, val: &Self::Element) -> Self::Element {
        debug_assert_eq!(1 << self.log2_padded_len, val.values.len());
        let mut result_values = Vec::with_capacity_in(val.values.len(), self.element_allocator.clone());
        result_values.extend(val.values.iter().map(|x| self.base_ring().clone_el(x)));
        return FreeAlgebraImplEl {
            values: result_values.into_boxed_slice()
        };
    }

    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
        for i in 0..self.rank() {
            self.base_ring().add_assign_ref(&mut lhs.values[i], &rhs.values[i]);
        }
    }

    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
        for (i, x) in (0..self.rank()).zip(rhs.values.iter()) {
            self.base_ring().add_assign_ref(&mut lhs.values[i], x);
        }
    }

    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
        for i in 0..self.rank() {
            self.base_ring().sub_assign_ref(&mut lhs.values[i], &rhs.values[i]);
        }
    }

    fn negate_inplace(&self, lhs: &mut Self::Element) {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        for i in 0..self.rank() {
            self.base_ring().negate_inplace(&mut lhs.values[i]);
        }
    }

    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
        self.mul_assign_ref(lhs, &rhs)
    }

    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
        *lhs = self.fma(lhs, rhs, self.zero());
    }

    fn fma(&self, lhs: &Self::Element, rhs: &Self::Element, summand: Self::Element) -> Self::Element {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, summand.values.len());
        let mut tmp = summand.values.into_vec();
        tmp.resize_with(2 << self.log2_padded_len, || self.base_ring.zero());
        self.convolution.compute_convolution(&lhs.values[..], &rhs.values[..], &mut tmp[..], self.base_ring());
        self.reduce_mod_poly(&mut tmp);
        tmp.truncate(1 << self.log2_padded_len);
        for i in self.rank()..(1 << self.log2_padded_len) {
            tmp[i] = self.base_ring().zero();
        }
        return FreeAlgebraImplEl {
            values: tmp.into_boxed_slice()
        };
    }
    
    fn from_int(&self, value: i32) -> Self::Element {
        self.from(self.base_ring().int_hom().map(value))
    }

    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, rhs.values.len());
        (0..self.rank()).all(|i| self.base_ring().eq_el(&lhs.values[i], &rhs.values[i]))
    }

    fn is_zero(&self, value: &Self::Element) -> bool {
        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
        (0..self.rank()).all(|i| self.base_ring.is_zero(&value.values[i]))
    }

    fn is_one(&self, value: &Self::Element) -> bool {
        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
        self.base_ring().is_one(&value.values[0]) && (1..self.rank()).all(|i| self.base_ring.is_zero(&value.values[i]))
    }

    fn is_neg_one(&self, value: &Self::Element) -> bool {
        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
        self.base_ring().is_neg_one(&value.values[0]) && (1..self.rank()).all(|i| self.base_ring.is_zero(&value.values[i]))
    }

    fn is_commutative(&self) -> bool {
        self.base_ring().is_commutative()
    }

    fn is_noetherian(&self) -> bool {
        self.base_ring().is_noetherian()
    }

    fn is_approximate(&self) -> bool {
        self.base_ring().get_ring().is_approximate()
    }

    fn dbg<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
        self.dbg_within(value, out, EnvBindingStrength::Weakest)
    }

    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, env: EnvBindingStrength) -> std::fmt::Result {
        debug_assert_eq!(1 << self.log2_padded_len, value.values.len());
        let poly_ring = DensePolyRing::new(self.base_ring(), self.gen_name);
        poly_ring.get_ring().dbg_within(&RingRef::new(self).poly_repr(&poly_ring, value, &self.base_ring().identity()), out, env)
    }

    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        for i in 0..self.rank() {
            self.base_ring().int_hom().mul_assign_map(&mut lhs.values[i], rhs);
        }
    }

    fn fma_int(&self, lhs: &Self::Element, rhs: i32, summand: Self::Element) -> Self::Element {
        debug_assert_eq!(1 << self.log2_padded_len, lhs.values.len());
        debug_assert_eq!(1 << self.log2_padded_len, summand.values.len());
        let mut result = Vec::new_in(self.allocator().clone());
        result.extend(summand.values.into_iter().enumerate().map(|(i, x)| self.base_ring().int_hom().fma_map(&lhs.values[i], &rhs, x)));
        return FreeAlgebraImplEl {
            values: result.into_boxed_slice()
        };
    }

    fn characteristic<I: IntegerRingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
        where I::Type: IntegerRing
    {
        self.base_ring().characteristic(ZZ)
    }

    fn square(&self, value: &mut Self::Element) {
        let mut tmp = Vec::with_capacity_in(2 << self.log2_padded_len, self.element_allocator.clone());
        tmp.resize_with(2 << self.log2_padded_len, || self.base_ring().zero());
        let x_prepared = self.convolution.prepare_convolution_operand(&value.values[..], Some(2 * self.rank()), self.base_ring());
        self.convolution.compute_convolution_prepared(&value.values[..], Some(&x_prepared), &value.values[..], Some(&x_prepared), &mut tmp, self.base_ring());
        self.reduce_mod_poly(&mut tmp);
        for i in 0..self.rank() {
            value.values[i] = std::mem::replace(&mut tmp[i], self.base_ring().zero());
        }
    }
}

impl<R, V, A, C> RingExtension for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    type BaseRing = R;
    
    fn base_ring<'a>(&'a self) -> &'a Self::BaseRing {
        &self.base_ring
    }

    fn from(&self, x: El<Self::BaseRing>) -> Self::Element {
        let mut result_values = Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone());
        result_values.push(x);
        result_values.extend((0..((1 << self.log2_padded_len) - 1)).map(|_| self.base_ring().zero()));
        return FreeAlgebraImplEl {
            values: result_values.into_boxed_slice()
        };
    }

    fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
        for i in 0..self.rank() {
            self.base_ring().mul_assign_ref(&mut lhs.values[i], rhs);
        }
    }

    fn fma_base(&self, lhs: &Self::Element, rhs: &El<Self::BaseRing>, summand: Self::Element) -> Self::Element {
        let mut new = Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone());
        new.extend(summand.values.into_iter().take(self.rank()).enumerate().map(|(i, x)| self.base_ring.fma(&lhs.values[i], rhs, x)));
        new.resize_with(1 << self.log2_padded_len, || self.base_ring().zero());
        return FreeAlgebraImplEl {
            values: new.into_boxed_slice()
        };
    }
}

///
/// It seems like a good idea to also implement [`DivisibilityRing::prepare_divisor()`]
/// and the prepared division functions here. However, currently the interface of
/// [`LinSolveRing`] does not support this. I am not yet sure what is the best approach
/// here, but it seems unlikely that this can be done properly without a breaking release
///  - Either change [`LinSolveRing`] to support "factorizations" of matrices, or rather
///    the equivalent to "prepared divisors" of matrices
///  - Implement [`DivisibilityRing::prepare_divisor()`] only for `R::Type: [`PrincipalIdealRing`]`,
///    which however requires specialization or a specialization workaround
/// 
/// TODO: Decide and implement on the next breaking release
/// 
impl<R, V, A, C> DivisibilityRing for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        R::Type: LinSolveRing,
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
        let mut mul_matrix: OwnedMatrix<_, _> = create_multiplication_matrix(RingRef::new(self), rhs, self.allocator().clone());
        let mut lhs_matrix: OwnedMatrix<_, _> = OwnedMatrix::zero_in(self.rank(), 1, self.base_ring(), self.allocator().clone());
        let data = self.wrt_canonical_basis(&lhs);
        for j in 0..self.rank() {
            *lhs_matrix.at_mut(j, 0) = data.at(j);
        }
        let mut solution: OwnedMatrix<_, _> = OwnedMatrix::zero_in(self.rank(), 1, self.base_ring(), self.allocator().clone());
        let has_sol = self.base_ring().get_ring().solve_right(mul_matrix.data_mut(), lhs_matrix.data_mut(), solution.data_mut(), Global);
        if has_sol.is_solved() {
            return Some(self.from_canonical_basis((0..self.rank()).map(|i| self.base_ring().clone_el(solution.at(i, 0)))));
        } else {
            return None;
        }
    }

    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
        where I: Iterator<Item = &'a Self::Element>, 
            Self: 'a
    {
        self.base_ring().get_ring().balance_factor(elements.flat_map(|x| x.values.iter())).map(|c| RingRef::new(self).inclusion().map(c))
    }

    default fn invert(&self, el: &Self::Element) -> Option<Self::Element> {
        self.checked_left_div(&self.one(), el)
    }
}

impl<R, V, A, C> Debug for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore + Debug, 
        V: VectorView<El<R>>, 
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        let poly_ring = DensePolyRing::new(self.base_ring(), self.gen_name);
        f.debug_struct("FreeAlgebraImplBase")
            .field("base_ring", &self.base_ring)
            .field("modulus", &poly_ring.format(&RingRef::new(self).generating_poly(&poly_ring, self.base_ring.identity())))
            .finish()
    }
}

impl<R, V> Serialize for FreeAlgebraImplBase<R, V, Global, KaratsubaAlgorithm>
    where R: RingStore + Serialize, 
        R::Type: SerializableElementRing,
        V: VectorView<El<R>>,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where S: Serializer
    {
        let poly_ring = DensePolyRing::new(self.base_ring(), "X");
        SerializableNewtypeStruct::new("FreeAlgebraImpl", (self.base_ring(), SerializeOwnedWithRing::new(RingRef::new(self).generating_poly(&poly_ring, self.base_ring().identity()), poly_ring))).serialize(serializer)
    }
}

impl<'de, R> Deserialize<'de> for FreeAlgebraImplBase<R, SparseMapVector<R>, Global, KaratsubaAlgorithm>
    where R: RingStore + Deserialize<'de> + Clone, 
        R::Type: SerializableElementRing,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where D: Deserializer<'de>
    {
        let ring_cell = OnceCell::new();
        let poly = <_ as DeserializeSeed<'de>>::deserialize(DeserializeSeedNewtypeStruct::new("FreeAlgebraImpl", DeserializeSeedDependentTuple::new(PhantomData::<R>, |ring| {
            let poly_ring = DensePolyRing::new(ring, "X");
            ring_cell.set(poly_ring).ok().unwrap();
            DeserializeWithRing::new(ring_cell.get().unwrap())
        })), deserializer)?;
        let poly_ring = ring_cell.into_inner().unwrap();
        assert!(poly_ring.base_ring().is_one(poly_ring.lc(&poly).unwrap()));
        let rank = poly_ring.degree(&poly).unwrap();
        let mut x_pow_rank = SparseMapVector::new(rank, (*poly_ring.base_ring()).clone());
        for (c, i) in poly_ring.terms(&poly) {
            *x_pow_rank.at_mut(i) = poly_ring.base_ring().negate(poly_ring.base_ring().clone_el(c));
        }
        _ = x_pow_rank.at_mut(0);
        return Ok(FreeAlgebraImpl::new_with_convolution(poly_ring.into().into_base_ring(), rank, x_pow_rank, "θ", Global, STANDARD_CONVOLUTION).into());
    }
}

impl<'de, R> Deserialize<'de> for FreeAlgebraImplBase<R, Vec<El<R>>, Global, KaratsubaAlgorithm>
    where R: RingStore + Deserialize<'de>, 
        R::Type: SerializableElementRing
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where D: Deserializer<'de>
    {
        let ring_cell = OnceCell::new();
        let poly = <_ as DeserializeSeed<'de>>::deserialize(DeserializeSeedNewtypeStruct::new("FreeAlgebraImpl", DeserializeSeedDependentTuple::new(PhantomData::<R>, |ring| {
            let poly_ring = DensePolyRing::new(ring, "X");
            ring_cell.set(poly_ring).ok().unwrap();
            DeserializeWithRing::new(ring_cell.get().unwrap())
        })), deserializer)?;
        let poly_ring = ring_cell.into_inner().unwrap();
        assert!(poly_ring.base_ring().is_one(poly_ring.lc(&poly).unwrap()));
        let rank = poly_ring.degree(&poly).unwrap();
        let x_pow_rank = (0..rank).map(|i| poly_ring.base_ring().negate(poly_ring.base_ring().clone_el(poly_ring.coefficient_at(&poly, i)))).collect::<Vec<_>>();
        return Ok(FreeAlgebraImpl::new_with_convolution(poly_ring.into().into_base_ring(), rank, x_pow_rank, "θ", Global, STANDARD_CONVOLUTION).into());
    }
}

impl<R, V, A, C> SerializableElementRing for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>,
        R::Type: SerializableElementRing
{
    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
        where D: Deserializer<'de>
    {
        // TODO: find better serialization name
        DeserializeSeedNewtypeStruct::new("ExtensionRingEl", DeserializeSeedSeq::new(
            std::iter::repeat(DeserializeWithRing::new(self.base_ring())).take(self.rank() + 1),
            Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone()),
            |mut current, next| { current.push(next); current }
        )).deserialize(deserializer).map(|mut values| {
            values.resize_with(1 << self.log2_padded_len, || self.base_ring().zero());
            FreeAlgebraImplEl { values: values.into_boxed_slice() }
        })
    }

    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
        where S: Serializer
    {
        debug_assert_eq!(1 << self.log2_padded_len, el.values.len());
        SerializableNewtypeStruct::new("ExtensionRingEl", SerializableSeq::new_with_len(
            (0..self.rank()).map(|i| SerializeWithRing::new(&el.values[i], self.base_ring())), self.rank()
        )).serialize(serializer)
    }
}

impl<R, V, A, C> FreeAlgebra for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    type VectorRepresentation<'a> = CloneElFn<&'a [El<R>], El<R>, CloneRingEl<&'a R>>
        where Self: 'a;

    fn canonical_gen(&self) -> Self::Element {
        if self.rank() == 1 {
            if self.x_pow_rank.len() == 1 {
                self.from_canonical_basis([self.base_ring.clone_el(self.x_pow_rank.at(0))])
            } else {
                assert!(self.x_pow_rank.len() == 0);
                self.zero()
            }
        } else {
            self.from_canonical_basis((0..self.rank()).map(|i| if i == 1 { self.base_ring.one() } else { self.base_ring.zero() }))
        }
    }

    fn wrt_canonical_basis<'a>(&'a self, el: &'a Self::Element) -> Self::VectorRepresentation<'a> {
        (&el.values[..self.rank]).clone_ring_els(self.base_ring())
    }

    fn from_canonical_basis<W>(&self, vec: W) -> Self::Element
        where W: IntoIterator<Item = El<Self::BaseRing>>,
            W::IntoIter: DoubleEndedIterator
    {
        let mut given_len = 0;
        let mut vec_it = vec.into_iter().inspect(|_| given_len += 1);
        let mut result = Vec::with_capacity_in(1 << self.log2_padded_len, self.element_allocator.clone());
        result.extend(vec_it.by_ref());
        result.extend((0..((1 << self.log2_padded_len) - self.rank())).map(|_| self.base_ring().zero()));
        assert!(vec_it.next().is_none());
        assert_eq!(given_len, self.rank());
        FreeAlgebraImplEl { values: result.into_boxed_slice() }
    }

    fn rank(&self) -> usize {
        self.rank
    }

    fn mul_assign_gen_power(&self, el: &mut Self::Element, power: usize) {
        let mut gen_pow_d = Vec::new_in(self.allocator().clone());
        gen_pow_d.extend(self.x_pow_rank.as_iter().map(|c| self.base_ring.clone_el(c)));
        gen_pow_d.resize_with(1 << self.log2_padded_len, || self.base_ring.zero());

        if power % self.rank() != 0 {
            let mut gen_pow_rem = Vec::new_in(self.allocator().clone());
            gen_pow_rem.extend((0..((power % self.rank()) - 1)).map(|_| self.base_ring.zero()));
            gen_pow_rem.push(self.base_ring.one());
            gen_pow_rem.resize_with(1 << self.log2_padded_len, || self.base_ring.zero());
            *el = self.prod([
                FreeAlgebraImplEl { values: replace(&mut el.values, Box::new_in([], self.allocator().clone())) },
                RingValue::from_ref(self).pow(FreeAlgebraImplEl { values: gen_pow_d.into_boxed_slice() }, power / self.rank),
                FreeAlgebraImplEl { values: gen_pow_rem.into_boxed_slice() },
            ]);
        } else {
            self.mul_assign(
                el,
                RingValue::from_ref(self).pow(FreeAlgebraImplEl { values: gen_pow_d.into_boxed_slice() }, power / self.rank),
            );
        }
    }
}

impl<R, V, A, C> HashableElRing for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        R::Type: HashableElRing,
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
        // this looks very simple, but I believe this is also the right implementation;
        // in particular, we assume that elements whose hashes are compared (e.g. because
        // they are in the same hashtable) belong to the same ring - after all, this is
        // also how we implement equality and all other operations. Hence, it does not
        // make sense to hash ring-specific info (like the rank). Additionally, hashes
        // in Rust are assumed to have no prefix-collisions, thus we don't need to insert
        // separators between elements, compare in particular [`Hash::hash_slice()`].
        for x in &el.values[..self.rank()] {
            self.base_ring().get_ring().hash(x, h)
        }
    }
}

///
/// Function that creates a [`FreeAlgebraImplEl`] from its canonical basis
/// representation.
/// 
/// Used by the implementation of [`FiniteRing::elements()`] for [`FreeAlgebraImplBase`].
/// 
pub struct WRTCanonicalBasisElementCreator<'a, R, V, A, C>
    where R: RingStore, 
        R::Type: FiniteRing, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    base_ring: &'a FreeAlgebraImplBase<R, V, A, C>
}

impl<'a, R, V, A, C> Clone for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
    where R: RingStore, 
        R::Type: FiniteRing, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    fn clone(&self) -> Self { *self }
}

impl<'a, 'b, R, V, A, C> FnOnce<(&'b [El<R>], )> for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
    where R: RingStore, 
        R::Type: FiniteRing, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    type Output = El<FreeAlgebraImpl<R, V, A, C>>;

    extern "rust-call" fn call_once(mut self, args: (&'b [El<R>], )) -> Self::Output {
        self.call_mut(args)
    }
}

impl<'a, 'b, R, V, A, C> FnMut<(&'b [El<R>], )> for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
    where R: RingStore, 
        R::Type: FiniteRing, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    extern "rust-call" fn call_mut(&mut self, args: (&'b [El<R>], )) -> Self::Output {
        self.base_ring.from_canonical_basis(args.0.iter().map(|x| self.base_ring.base_ring().clone_el(x)))
    }
}

impl<'a, R, V, A, C> Copy for WRTCanonicalBasisElementCreator<'a, R, V, A, C>
    where R: RingStore, 
        R::Type: FiniteRing, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{}

impl<R, V, A, C> FiniteRingSpecializable for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore,
        R::Type: FiniteRingSpecializable, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output {
        struct OpWrapper<R, V, A, C, O>
            where R: RingStore,
                R::Type: FiniteRingSpecializable, 
                V: VectorView<El<R>>,
                A: Allocator + Clone,
                C: ConvolutionAlgorithm<R::Type>,
                O: FiniteRingOperation<FreeAlgebraImplBase<R, V, A, C>>
        {
            operation: O,
            ring: PhantomData<FreeAlgebraImpl<R, V, A, C>>
        }

        impl<R, V, A, C, O> FiniteRingOperation<R::Type> for OpWrapper<R, V, A, C, O>
            where R: RingStore,
                R::Type: FiniteRingSpecializable, 
                V: VectorView<El<R>>,
                A: Allocator + Clone,
                C: ConvolutionAlgorithm<R::Type>,
                O: FiniteRingOperation<FreeAlgebraImplBase<R, V, A, C>>
        {
            type Output = O::Output;
            fn execute(self) -> Self::Output where R::Type:FiniteRing {
                self.operation.execute()
            }
            fn fallback(self) -> Self::Output {
                self.operation.fallback()
            }
        }

        <R::Type as FiniteRingSpecializable>::specialize(OpWrapper { operation: op, ring: PhantomData })
    }
}

impl<R, V, A, C> FiniteRing for FreeAlgebraImplBase<R, V, A, C>
    where R: RingStore, 
        R::Type: FiniteRing, 
        V: VectorView<El<R>>,
        A: Allocator + Clone,
        C: ConvolutionAlgorithm<R::Type>
{
    type ElementsIter<'a> = MultiProduct<<R::Type as FiniteRing>::ElementsIter<'a>, WRTCanonicalBasisElementCreator<'a, R, V, A, C>, CloneRingEl<&'a R>, Self::Element>
        where Self: 'a;

    fn elements<'a>(&'a self) -> Self::ElementsIter<'a> {
        multi_cartesian_product((0..self.rank()).map(|_| self.base_ring().elements()), WRTCanonicalBasisElementCreator { base_ring: self }, CloneRingEl(self.base_ring()))
    }

    fn size<I: IntegerRingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
        where I::Type: IntegerRing
    {
        let base_ring_size = self.base_ring().size(ZZ)?;
        if ZZ.get_ring().representable_bits().is_none() || ZZ.abs_log2_ceil(&base_ring_size).unwrap() * self.rank() < ZZ.get_ring().representable_bits().unwrap() {
            Some(ZZ.pow(base_ring_size, self.rank()))
        } else {
            None
        }
    }

    fn random_element<G: FnMut() -> u64>(&self, mut rng: G) -> <Self as RingBase>::Element {
        self.from_canonical_basis((0..self.rank()).map(|_| self.base_ring().random_element(&mut rng)))
    }
}

impl_field_wrap_unwrap_homs!{
    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
            R2::Type: CanHomFrom<R1::Type>
}

impl_field_wrap_unwrap_isos!{
    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
            R2::Type: CanIsoFromTo<R1::Type>
}

impl_localpir_wrap_unwrap_homs!{
    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
            R2::Type: CanHomFrom<R1::Type>
}

impl_localpir_wrap_unwrap_isos!{
    <{R1, V1, A1, C1, R2, V2, A2, C2}> FreeAlgebraImplBase<R1, V1, A1, C1>, FreeAlgebraImplBase<R2, V2, A2, C2>
        where R1: RingStore, R1::Type: LinSolveRing, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
            R2: RingStore, R2::Type: LinSolveRing, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
            R2::Type: CanIsoFromTo<R1::Type>
}

impl<R1, V1, A1, C1, R2, V2, A2, C2> CanHomFrom<FreeAlgebraImplBase<R1, V1, A1, C1>> for FreeAlgebraImplBase<R2, V2, A2, C2>
    where R1: RingStore, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
        R2: RingStore, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
        R2::Type: CanHomFrom<R1::Type>
{
    type Homomorphism = <R2::Type as CanHomFrom<R1::Type>>::Homomorphism;

    fn has_canonical_hom(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>) -> Option<Self::Homomorphism> {
        if self.rank() == from.rank() {
            let hom = self.base_ring.get_ring().has_canonical_hom(from.base_ring.get_ring())?;
            if (0..self.rank()).all(|i| (i >= self.x_pow_rank.len() && i >= from.x_pow_rank.len()) ||
                (i >= self.x_pow_rank.len() && from.base_ring().is_zero(from.x_pow_rank.at(i))) ||
                (i >= from.x_pow_rank.len() && self.base_ring().is_zero(self.x_pow_rank.at(i))) ||
                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))
            ) {
                Some(hom)
            } else {
                None
            }
        } else {
            None
        }
    }

    fn map_in(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>, el: <FreeAlgebraImplBase<R1, V1, A1> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
        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)))
    }
}

impl<R1, V1, A1, C1, R2, V2, A2, C2> CanIsoFromTo<FreeAlgebraImplBase<R1, V1, A1, C1>> for FreeAlgebraImplBase<R2, V2, A2, C2>
    where R1: RingStore, V1: VectorView<El<R1>>, A1: Allocator + Clone, C1: ConvolutionAlgorithm<R1::Type>,
        R2: RingStore, V2: VectorView<El<R2>>, A2: Allocator + Clone, C2: ConvolutionAlgorithm<R2::Type>,
        R2::Type: CanIsoFromTo<R1::Type>
{
    type Isomorphism = <R2::Type as CanIsoFromTo<R1::Type>>::Isomorphism;

    fn has_canonical_iso(&self, from: &FreeAlgebraImplBase<R1, V1, A1, C1>) -> Option<Self::Isomorphism> {
        if self.rank() == from.rank() {
            let iso = self.base_ring.get_ring().has_canonical_iso(from.base_ring.get_ring())?;
            if (0..self.rank()).all(|i|(i >= self.x_pow_rank.len() && i >= from.x_pow_rank.len()) ||
                (i >= self.x_pow_rank.len() && from.base_ring().is_zero(from.x_pow_rank.at(i))) ||
                (i >= from.x_pow_rank.len() && self.base_ring().is_zero(self.x_pow_rank.at(i))) ||
                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))
            ) {
                Some(iso)
            } else {
                None
            }
        } else {
            None
        }
    }

    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 {
        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)))
    }
}

#[cfg(test)]
use crate::rings::zn::zn_64::{Zn, ZnEl};
#[cfg(test)]
use crate::rings::zn::ZnRingStore;
#[cfg(test)]
use crate::rings::zn::zn_static;
#[cfg(test)]
use crate::algorithms::convolution::fft::FFTConvolution;

#[cfg(test)]
fn test_ring0_and_elements() -> (FreeAlgebraImpl<Zn, Vec<ZnEl>>, Vec<FreeAlgebraImplEl<Zn>>) {
    let R = FreeAlgebraImpl::new(Zn::new(7), 1, vec![Zn::new(7).neg_one()]);
    let elements = R.elements().collect();
    return (R, elements);
}

#[cfg(test)]
fn test_ring1_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, [i64; 2]>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
    let ZZ = StaticRing::<i64>::RING;
    let R = FreeAlgebraImpl::new(ZZ, 2, [1, 1]);
    let mut elements = Vec::new();
    for a in -3..=3 {
        for b in -3..=3 {
            elements.push(R.from_canonical_basis([a, b]));
        }
    }
    return (R, elements);
}

#[cfg(test)]
fn test_ring2_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, Vec<i64>>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
    let ZZ = StaticRing::<i64>::RING;
    let R = FreeAlgebraImpl::new(ZZ, 3, vec![1, -1, 1]);
    let mut elements = Vec::new();
    for a in [-2, 0, 1, 2] {
        for b in [-2, 0, 2] {
            for c in [-2, 0, 2] {
                elements.push(R.from_canonical_basis([a, b, c]));
            }
        }
    }
    return (R, elements);
}

#[cfg(test)]
fn test_ring3_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, Vec<i64>>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
    let ZZ = StaticRing::<i64>::RING;
    let R = FreeAlgebraImpl::new(ZZ, 3, vec![1]);
    let mut elements = Vec::new();
    for a in [-2, 0, 1, 2] {
        for b in [-2, 0, 2] {
            for c in [-2, 0, 2] {
                elements.push(R.from_canonical_basis([a, b, c]));
            }
        }
    }
    return (R, elements);
}

#[cfg(test)]
fn test_ring4_and_elements() -> (FreeAlgebraImpl<StaticRing::<i64>, SparseMapVector<StaticRing<i64>>>, Vec<FreeAlgebraImplEl<StaticRing<i64>>>) {
    let ZZ = StaticRing::<i64>::RING;
    // ZZ[X]/(X^3 - X)
    let mut modulus = SparseMapVector::new(3, StaticRing::<i64>::RING);
    *modulus.at_mut(1) = 1;
    let R = FreeAlgebraImpl::new(ZZ, 3, modulus);
    let mut elements = Vec::new();
    for a in [-2, 0, 1, 2] {
        for b in [-2, 0, 2] {
            for c in [-2, 0, 2] {
                elements.push(R.from_canonical_basis([a, b, c]));
            }
        }
    }
    return (R, elements);
}

#[test]
fn test_sparse() {
    let (ring, _) = test_ring4_and_elements();
    assert_el_eq!(ring, ring.canonical_gen(), ring.pow(ring.canonical_gen(), 3));
}

#[test]
fn test_ring_axioms() {
    // let (ring, els) = test_ring0_and_elements();
    // crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
    // let (ring, els) = test_ring1_and_elements();
    // crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
    let (ring, els) = test_ring2_and_elements();
    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
    let (ring, els) = test_ring3_and_elements();
    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
    let (ring, els) = test_ring4_and_elements();
    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());
    
    let (ring, els) = test_ring2_and_elements();
    let ring = ring.into().set_convolution(FFTConvolution::new_with_alloc(Global));
    crate::ring::generic_tests::test_ring_axioms(ring, els.into_iter());

    let base_ring = zn_static::Fp::<257>::RING;
    let x_pow_rank = vec![base_ring.neg_one(); 64];
    let ring = FreeAlgebraImpl::new(base_ring, 64, x_pow_rank);
    let mut rng = oorandom::Rand64::new(1);
    let els = (0..10).map(|_| ring.from_canonical_basis((0..64).map(|_| ring.base_ring().random_element(|| rng.rand_u64()))));
    crate::ring::generic_tests::test_ring_axioms(&ring, els);
}

#[test]
fn test_rank_1_ring() {
    let base_ring = Zn::new(5).as_field().ok().unwrap();
    let ring = FreeAlgebraImpl::new(base_ring, 1, [base_ring.int_hom().map(1)]).as_field().ok().unwrap();
    crate::field::generic_tests::test_field_axioms(&ring, ring.elements());

    assert_el_eq!(ring, ring.one(), ring.canonical_gen());
}

#[test]
fn test_free_algebra_axioms() {
    let (ring, _) = test_ring0_and_elements();
    super::generic_tests::test_free_algebra_axioms(ring);
    let (ring, _) = test_ring1_and_elements();
    super::generic_tests::test_free_algebra_axioms(ring);
    let (ring, _) = test_ring2_and_elements();
    super::generic_tests::test_free_algebra_axioms(ring);
    let (ring, _) = test_ring3_and_elements();
    super::generic_tests::test_free_algebra_axioms(ring);
    let (ring, _) = test_ring4_and_elements();
    super::generic_tests::test_free_algebra_axioms(ring);
}

#[test]
fn test_division() {
    let base_ring = Zn::new(4);
    let i = base_ring.int_hom();
    let ring = FreeAlgebraImpl::new(base_ring, 2, [i.map(-1), i.map(-1)]);

    assert_el_eq!(ring, 
        &ring.from_canonical_basis([i.map(1), i.map(3)]), 
        &ring.checked_div(&ring.one(), &ring.from_canonical_basis([i.map(2), i.map(3)])).unwrap()
    );

    let a = ring.from_canonical_basis([i.map(2), i.map(2)]);
    let b = ring.from_canonical_basis([i.map(0), i.map(2)]);
    assert_el_eq!(ring, a, ring.mul(ring.checked_div(&a, &b).unwrap(), b));

    assert!(ring.checked_div(&ring.one(), &a).is_none());
}

#[test]
fn test_division_ring_of_integers() {
    let base_ring = StaticRing::<i64>::RING;
    let ring = FreeAlgebraImpl::new(base_ring, 2, [11, 0]);

    // the solution to Pell's equation is 10^2 - 3^2 * 11 = 1
    let u = ring.from_canonical_basis([10, 3]);
    let u_inv = ring.from_canonical_basis([10, -3]);

    assert_el_eq!(ring, u_inv, ring.checked_div(&ring.one(), &u).unwrap());
    assert_el_eq!(ring, ring.pow(u_inv, 3), &ring.checked_div(&ring.one(), &ring.pow(u, 3)).unwrap());

    assert!(ring.checked_div(&ring.from_canonical_basis([2, 0]), &ring.from_canonical_basis([3, 0])).is_none());
}

#[test]
fn test_divisibility_axioms() {
    let (ring, els) = test_ring0_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
    let (ring, els) = test_ring1_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
    let (ring, els) = test_ring2_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
    let (ring, els) = test_ring3_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
    let (ring, els) = test_ring4_and_elements();
    crate::divisibility::generic_tests::test_divisibility_axioms(ring, els.into_iter());
}

#[test]
fn test_cubic_mul() {
    let base_ring = zn_static::Zn::<256>::RING;
    let modulo = base_ring.int_hom();
    let ring = FreeAlgebraImpl::new(base_ring, 3, [modulo.map(-1), modulo.map(-1), modulo.map(-1)]);
    let a = ring.from_canonical_basis([modulo.map(0), modulo.map(-1), modulo.map(-1)]);
    let b = ring.from_canonical_basis([modulo.map(-1), modulo.map(-2), modulo.map(-1)]);
    assert_el_eq!(ring, b, ring.pow(a, 2));
}

#[test]
fn test_as_field() {
    let base_ring = Zn::new(5).as_field().ok().unwrap();
    let ring = FreeAlgebraImpl::new(base_ring, 1, [base_ring.int_hom().map(1)]).as_field().ok().unwrap();
    crate::field::generic_tests::test_field_axioms(&ring, ring.elements());

    let base_ring = Zn::new(3).as_field().ok().unwrap();
    let ring = FreeAlgebraImpl::new(base_ring, 2, [base_ring.int_hom().map(2)]).as_field().ok().unwrap();
    crate::field::generic_tests::test_field_axioms(&ring, ring.elements());

    assert!(FreeAlgebraImpl::new(base_ring, 2, [base_ring.int_hom().map(1)]).as_field().is_err());
}

#[test]
fn test_serialization() {
    let (ring, els) = test_ring0_and_elements();
    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
    let (ring, els) = test_ring1_and_elements();
    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
    let (ring, els) = test_ring2_and_elements();
    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
    let (ring, els) = test_ring3_and_elements();
    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
    let (ring, els) = test_ring4_and_elements();
    crate::serialization::generic_tests::test_serialization(ring, els.into_iter());
}

#[test]
#[should_panic]
fn test_from_canonical_basis_enforce_len() {
    let (ring, _) = test_ring1_and_elements();
    _ = ring.from_canonical_basis([0, 1, 2]);
}

#[test]
fn test_serialize_deserialize() {
    crate::serialization::generic_tests::test_serialize_deserialize(test_ring0_and_elements().0.into());
    crate::serialization::generic_tests::test_serialize_deserialize(test_ring2_and_elements().0.into());
    crate::serialization::generic_tests::test_serialize_deserialize(test_ring3_and_elements().0.into());
}