Struct he_ring::complexfft::complex_fft_ring::ComplexFFTBasedRingBase

pub struct ComplexFFTBasedRingBase<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> { /* private fields */ }

Implementation of rings Z[X]/(f(X), q) that uses a GeneralizedFFT for fast arithmetic.

The concrete ring (i.e. the polynomial f) is determined by the used GeneralizedFFT. In the most general case, you can use ComplexFFTBasedRingBase::from_generalized_fft() to create an instance for any f, but in the case of cyclotomics (e.g. when using crate::complexfft::pow2_cyclotomic::Pow2CyclotomicFFT), simpler creation functions are provided.

Example

type TheRing = ComplexFFTBasedRing<Pow2CyclotomicFFT<Zn, cooley_tuckey::FFTTableCooleyTuckey<Complex64>>, DefaultMemoryProvider, DefaultMemoryProvider>;
 
// the ring `F7[X]/(X^8 + 1)`
let R = <TheRing as RingStore>::Type::new(Zn::new(7), 3, default_memory_provider!(), default_memory_provider!());
let root_of_unity = R.canonical_gen();
assert_eq!(8, R.rank());
assert_eq!(16, R.n());
assert_el_eq!(&R, &R.neg_one(), &R.pow(root_of_unity, 8));
 
// instead of this, we can also explicity create the `GeneralizedFFT`
let generalized_fft: Pow2CyclotomicFFT<Zn, cooley_tuckey::FFTTableCooleyTuckey<Complex64>> = Pow2CyclotomicFFT::create(
    Zn::new(7),
    cooley_tuckey::FFTTableCooleyTuckey::for_complex(Complex64::RING, 3)
);
let R = RingValue::from(<TheRing as RingStore>::Type::from_generalized_fft(generalized_fft, default_memory_provider!(), default_memory_provider!()));
assert_eq!(8, R.rank());
assert_eq!(16, R.n());
assert_el_eq!(&R, &R.neg_one(), &R.pow(R.canonical_gen(), 8));

Implementations

impl<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> ComplexFFTBasedRingBase<F, M_Zn, M_CC>

pub fn from_generalized_fft( data: F, memory_provider_zn: M_Zn, memory_provider_cc: M_CC, ) -> Self

pub fn generalized_fft(&self) -> &F

pub fn memory_provider_zn(&self) -> &M_Zn

pub fn memory_provider_cc(&self) -> &M_CC

impl<R: ZnRingStore, M_Zn, M_CC> ComplexFFTBasedRingBase<Pow2CyclotomicFFT<R, FFTTableCooleyTuckey<Complex64>>, M_Zn, M_CC>

where R::Type: ZnRing, M_Zn: MemoryProvider<El<R>>, M_CC: MemoryProvider<Complex64El>,

pub fn new( base_ring: R, log2_ring_degree: usize, memory_provider_zn: M_Zn, memory_provider_cc: M_CC, ) -> RingValue<Self>

impl<R, M_Zn, M_CC> ComplexFFTBasedRingBase<OddCyclotomicFFT<R, FFTTableBluestein<Complex64>>, M_Zn, M_CC>

where R::Type: ZnRing + DivisibilityRing + CanHomFrom<StaticRingBase<i64>>, R: Clone + ZnRingStore, M_Zn: MemoryProvider<El<R>>, M_CC: MemoryProvider<Complex64El>,

pub fn new( base_ring: R, n: usize, memory_provider_zn: M_Zn, memory_provider_cc: M_CC, ) -> RingValue<Self>

Trait Implementations

impl<F1, F2, M1_Zn, M2_Zn, M1_CC, M2_CC> CanHomFrom<ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC>> for ComplexFFTBasedRingBase<F1, M1_Zn, M1_CC>

where F1: GeneralizedFFT + GeneralizedFFTSelfIso + GeneralizedFFTIso<F2>, F2: GeneralizedFFT + GeneralizedFFTSelfIso, M1_Zn: MemoryProvider<El<F1::BaseRingStore>>, M1_CC: MemoryProvider<Complex64El>, M2_Zn: MemoryProvider<El<F2::BaseRingStore>>, M2_CC: MemoryProvider<Complex64El>, F1::BaseRingBase: CanHomFrom<F2::BaseRingBase>,

type Homomorphism = <<F1 as GeneralizedFFT>::BaseRingBase as CanHomFrom<<F2 as GeneralizedFFT>::BaseRingBase>>::Homomorphism

fn has_canonical_hom( &self, from: &ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC>, ) -> Option<Self::Homomorphism>

fn map_in( &self, from: &ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC>, el: <ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC> as RingBase>::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn map_in_ref( &self, from: &S, el: &<S as RingBase>::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn mul_assign_map_in( &self, from: &S, lhs: &mut Self::Element, rhs: <S as RingBase>::Element, hom: &Self::Homomorphism, )

fn mul_assign_map_in_ref( &self, from: &S, lhs: &mut Self::Element, rhs: &<S as RingBase>::Element, hom: &Self::Homomorphism, )

impl<P, F, M_Zn, M_CC> CanHomFrom<P> for ComplexFFTBasedRingBase<F, M_Zn, M_CC>

where F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>, P: PolyRing, F::BaseRingBase: CanHomFrom<<P::BaseRing as RingStore>::Type>,

type Homomorphism = <<F as GeneralizedFFT>::BaseRingBase as CanHomFrom<<<P as RingExtension>::BaseRing as RingStore>::Type>>::Homomorphism

fn has_canonical_hom(&self, from: &P) -> Option<Self::Homomorphism>

fn map_in( &self, from: &P, el: <P as RingBase>::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn map_in_ref( &self, from: &P, el: &<P as RingBase>::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn mul_assign_map_in( &self, from: &S, lhs: &mut Self::Element, rhs: <S as RingBase>::Element, hom: &Self::Homomorphism, )

fn mul_assign_map_in_ref( &self, from: &S, lhs: &mut Self::Element, rhs: &<S as RingBase>::Element, hom: &Self::Homomorphism, )

impl<F1, F2, M1_Zn, M2_Zn, M1_CC, M2_CC> CanIsoFromTo<ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC>> for ComplexFFTBasedRingBase<F1, M1_Zn, M1_CC>

where F1: GeneralizedFFT + GeneralizedFFTSelfIso + GeneralizedFFTIso<F2>, F2: GeneralizedFFT + GeneralizedFFTSelfIso, M1_Zn: MemoryProvider<El<F1::BaseRingStore>>, M1_CC: MemoryProvider<Complex64El>, M2_Zn: MemoryProvider<El<F2::BaseRingStore>>, M2_CC: MemoryProvider<Complex64El>, F1::BaseRingBase: CanIsoFromTo<F2::BaseRingBase>,

type Isomorphism = <<F1 as GeneralizedFFT>::BaseRingBase as CanIsoFromTo<<F2 as GeneralizedFFT>::BaseRingBase>>::Isomorphism

fn has_canonical_iso( &self, from: &ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC>, ) -> Option<Self::Isomorphism>

fn map_out( &self, from: &ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC>, el: Self::Element, iso: &Self::Isomorphism, ) -> <ComplexFFTBasedRingBase<F2, M2_Zn, M2_CC> as RingBase>::Element

impl<R: ZnRingStore, F: FFTTable<Ring = Complex64> + ErrorEstimate, M_Zn, M_CC> CyclotomicRing for ComplexFFTBasedRingBase<OddCyclotomicFFT<R, F>, M_Zn, M_CC>

where R::Type: ZnRing + CanHomFrom<StaticRingBase<i64>>, M_Zn: MemoryProvider<El<R>>, M_CC: MemoryProvider<Complex64El>,

fn n(&self) -> usize

The cyclotomic order, i.e. the multiplicative order of self.canonical_gen(). The degree of this ring extension is phi(self.n()) where phi is Euler’s totient function.

impl<R: ZnRingStore, F: FFTTable<Ring = Complex64> + ErrorEstimate, M_Zn, M_CC> CyclotomicRing for ComplexFFTBasedRingBase<Pow2CyclotomicFFT<R, F>, M_Zn, M_CC>

where R::Type: ZnRing, M_Zn: MemoryProvider<El<R>>, M_CC: MemoryProvider<Complex64El>,

fn n(&self) -> usize

The cyclotomic order, i.e. the multiplicative order of self.canonical_gen(). The degree of this ring extension is phi(self.n()) where phi is Euler’s totient function.

impl<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> FiniteRing for ComplexFFTBasedRingBase<F, M_Zn, M_CC>

type ElementsIter<'a> = MultiProduct<<<F as GeneralizedFFT>::BaseRingBase as FiniteRing>::ElementsIter<'a>, WRTCanonicalBasisElementCreator<'a, F, M_Zn, M_CC>, RingElementClone<'a, <F as GeneralizedFFT>::BaseRingBase>, <ComplexFFTBasedRingBase<F, M_Zn, M_CC> as RingBase>::Element> where Self: 'a

fn elements<'a>(&'a self) -> Self::ElementsIter<'a>

fn random_element<G: FnMut() -> u64>(&self, rng: G) -> Self::Element

fn size<I: IntegerRingStore>(&self, ZZ: &I) -> Option<El<I>>

where I::Type: IntegerRing,

impl<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> FreeAlgebra for ComplexFFTBasedRingBase<F, M_Zn, M_CC>

type VectorRepresentation<'a> = RingElVectorViewFn<&'a <F as GeneralizedFFT>::BaseRingStore, &'a [<<<F as GeneralizedFFT>::BaseRingStore as RingStore>::Type as RingBase>::Element], <<<F as GeneralizedFFT>::BaseRingStore as RingStore>::Type as RingBase>::Element> where Self: 'a

fn canonical_gen(&self) -> Self::Element

fn rank(&self) -> usize

fn wrt_canonical_basis<'a>( &'a self, el: &'a Self::Element, ) -> Self::VectorRepresentation<'a>

fn from_canonical_basis<V>(&self, vec: V) -> Self::Element

where V: ExactSizeIterator<Item = <<Self::BaseRing as RingStore>::Type as RingBase>::Element> + DoubleEndedIterator + Iterator,

impl<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> PartialEq for ComplexFFTBasedRingBase<F, M_Zn, M_CC>

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> RingBase for ComplexFFTBasedRingBase<F, M_Zn, M_CC>

type Element = <M_Zn as MemoryProvider<<<<F as GeneralizedFFT>::BaseRingStore as RingStore>::Type as RingBase>::Element>>::Object

fn clone_el(&self, val: &Self::Element) -> Self::Element

fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn negate_inplace(&self, lhs: &mut Self::Element)

fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn from_int(&self, value: i32) -> Self::Element

fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

fn is_commutative(&self) -> bool

fn is_noetherian(&self) -> bool

fn dbg<'a>(&self, value: &Self::Element, out: &mut Formatter<'a>) -> Result

fn square(&self, value: &mut Self::Element)

fn pow_gen<I: IntegerRingStore>( &self, x: Self::Element, power: &El<I>, integers: I, ) -> Self::Element

where I::Type: IntegerRing,

Raises x to the power of an arbitrary, nonnegative integer given by a custom integer ring implementation.

fn characteristic<I: IntegerRingStore>(&self, ZZ: &I) -> Option<El<I>>

where I::Type: IntegerRing,

Returns the characteristic of this ring as an element of the given implementation of ZZ.

fn zero(&self) -> Self::Element

fn one(&self) -> Self::Element

fn neg_one(&self) -> Self::Element

fn is_zero(&self, value: &Self::Element) -> bool

fn is_one(&self, value: &Self::Element) -> bool

fn is_neg_one(&self, value: &Self::Element) -> bool

fn is_approximate(&self) -> bool

Returns whether this ring computes with approximations to elements. This would usually be the case for rings that are based on f32 or f64, to represent real or complex numbers.

fn negate(&self, value: Self::Element) -> Self::Element

fn sub_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32)

fn mul_int(&self, lhs: Self::Element, rhs: i32) -> Self::Element

fn mul_int_ref(&self, lhs: &Self::Element, rhs: i32) -> Self::Element

fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

Computes lhs := rhs - lhs.

fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

Computes lhs := rhs - lhs.

fn add_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn add_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn add_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn add(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn sub_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn mul_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn mul(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn sum<I>(&self, els: I) -> Self::Element

where I: Iterator<Item = Self::Element>,

fn prod<I>(&self, els: I) -> Self::Element

where I: Iterator<Item = Self::Element>,

impl<F: GeneralizedFFT + GeneralizedFFTSelfIso, M_Zn: MemoryProvider<El<F::BaseRingStore>>, M_CC: MemoryProvider<Complex64El>> RingExtension for ComplexFFTBasedRingBase<F, M_Zn, M_CC>

type BaseRing = <F as GeneralizedFFT>::BaseRingStore

fn base_ring<'a>(&'a self) -> &'a Self::BaseRing

fn from(&self, x: El<Self::BaseRing>) -> Self::Element

fn from_ref( &self, x: &<<Self::BaseRing as RingStore>::Type as RingBase>::Element, ) -> Self::Element

fn mul_assign_base( &self, lhs: &mut Self::Element, rhs: &<<Self::BaseRing as RingStore>::Type as RingBase>::Element, )

Computes lhs := lhs * rhs, where rhs is mapped into this ring via RingExtension::from_ref(). Note that this may be faster than self.mul_assign(lhs, self.from_ref(rhs)).