Struct NTTConvolution

pub struct NTTConvolution<R, A = Global>
where
    R: RingStore + Clone,
    R::Type: ZnRing,
    A: Allocator + Clone,
{ /* private fields */ }

Computes the convolution over a finite field that has suitable roots of unity using a power-of-two length FFT (sometimes called Number-Theoretic Transform, NTT in this context).

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

Implementations

impl<R, A> NTTConvolution<R, A>

where R: RingStore + Clone, R::Type: ZnRing, A: Allocator + Clone,

pub fn new_with(ring: R, allocator: A) -> Self

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

pub fn ring(&self) -> &R

Availability

This API is marked as unstable and is only available when the unstable-enable crate feature is enabled. This comes with no stability guarantees, and could be changed or removed at any time.

Trait Implementations

impl<R, A> ConvolutionAlgorithm<<R as RingStore>::Type> for NTTConvolution<R, A>

where R: RingStore + Clone, R::Type: ZnRing, A: Allocator + Clone,

fn supports_ring<S: RingStore<Type = R::Type> + Copy>(&self, ring: S) -> bool

Returns whether this convolution algorithm supports computations of the given ring.

fn compute_convolution<S: RingStore<Type = R::Type> + Copy, V1: VectorView<<R::Type as RingBase>::Element>, V2: VectorView<<R::Type as RingBase>::Element>>( &self, lhs: V1, rhs: V2, dst: &mut [El<R>], ring: S, )

Elementwise adds the convolution of lhs and rhs to dst.

fn specialize_prepared_convolution<F>(function: F) -> Result<F::Output, F>

where F: PreparedConvolutionOperation<Self, R::Type>,

If this convolution implements PreparedConvolutionAlgorithm, then the given function is called and its result is returned. Otherwise, Err is returned.

impl<R, A> PreparedConvolutionAlgorithm<<R as RingStore>::Type> for NTTConvolution<R, A>

where R: RingStore + Clone, R::Type: ZnRing, A: Allocator + Clone,

type PreparedConvolutionOperand = PreparedConvolutionOperand<R, A>

fn prepare_convolution_operand<S: RingStore<Type = R::Type> + Copy, V: VectorView<El<R>>>( &self, val: V, ring: S, ) -> Self::PreparedConvolutionOperand

fn compute_convolution_lhs_prepared<S: RingStore<Type = R::Type> + Copy, V: VectorView<El<R>>>( &self, lhs: &Self::PreparedConvolutionOperand, rhs: V, dst: &mut [El<R>], ring: S, )

fn compute_convolution_prepared<S: RingStore<Type = R::Type> + Copy>( &self, lhs: &Self::PreparedConvolutionOperand, rhs: &Self::PreparedConvolutionOperand, dst: &mut [El<R>], ring: S, )

fn compute_convolution_inner_product_prepared<'a, S, I>( &self, values: I, dst: &mut [El<R>], ring: S, )

where S: RingStore<Type = R::Type> + Copy, I: Iterator<Item = (&'a Self::PreparedConvolutionOperand, &'a Self::PreparedConvolutionOperand)>, Self: 'a, R: 'a, PreparedConvolutionOperand<R, A>: 'a,

fn compute_convolution_rhs_prepared<S, V>( &self, lhs: V, rhs: &Self::PreparedConvolutionOperand, dst: &mut [R::Element], ring: S, )

where S: RingStore<Type = R> + Copy, V: VectorView<R::Element>,

fn compute_convolution_inner_product_lhs_prepared<'a, S, I, V>( &self, values: I, dst: &mut [R::Element], ring: S, )

where S: RingStore<Type = R> + Copy, I: Iterator<Item = (&'a Self::PreparedConvolutionOperand, V)>, V: VectorView<R::Element>, Self: 'a, R: 'a, Self::PreparedConvolutionOperand: 'a,