Struct NTTConvolution

pub struct NTTConvolution<R_main, R_twiddle, H, A = Global>
where
    R_main: ?Sized + ZnRing,
    R_twiddle: ?Sized + ZnRing,
    H: Homomorphism<R_twiddle, R_main> + Clone,
    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> NTTConvolution<R::Type, R::Type, Identity<R>>

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

pub fn new(ring: R) -> 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.

impl<R_main, R_twiddle, H, A> NTTConvolution<R_main, R_twiddle, H, A>

where R_main: ?Sized + ZnRing, R_twiddle: ?Sized + ZnRing, H: Homomorphism<R_twiddle, R_main> + Clone, A: Allocator + Clone,

pub fn new_with(hom: H, 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) -> RingRef<'_, R_main>

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_main, R_twiddle, H, A> ConvolutionAlgorithm<R_main> for NTTConvolution<R_main, R_twiddle, H, A>

where R_main: ?Sized + ZnRing, R_twiddle: ?Sized + ZnRing, H: Homomorphism<R_twiddle, R_main> + Clone, A: Allocator + Clone,

type PreparedConvolutionOperand = PreparedConvolutionOperand<R_main, A>

Additional data associated to a list of ring elements, which can be used to compute a convolution where this list is one of the operands faster.

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

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

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

Elementwise adds the convolution of lhs and rhs to dst.

fn prepare_convolution_operand<S, V>( &self, val: V, length_hint: Option<usize>, ring: S, ) -> Self::PreparedConvolutionOperand

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

Takes an input list of values and computes an opaque ConvolutionAlgorithm::PreparedConvolutionOperand, which can be used to compute future convolutions with this list of values faster.

fn compute_convolution_prepared<S, V1, V2>( &self, lhs: V1, lhs_prep: Option<&Self::PreparedConvolutionOperand>, rhs: V2, rhs_prep: Option<&Self::PreparedConvolutionOperand>, dst: &mut [R_main::Element], ring: S, )

where S: RingStore<Type = R_main> + Copy, V1: VectorView<R_main::Element>, V2: VectorView<R_main::Element>,

Elementwise adds the convolution of lhs and rhs to dst. If provided, the given prepared convolution operands are used for a faster computation.

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

where S: RingStore<Type = R> + Copy, I: ExactSizeIterator<Item = (V1, Option<&'a Self::PreparedConvolutionOperand>, V2, Option<&'a Self::PreparedConvolutionOperand>)>, V1: VectorView<R::Element>, V2: VectorView<R::Element>, Self: 'a, R: 'a,

Computes a convolution for each tuple in the given sequence, and sums the result of each convolution to dst.