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 */ }

Available on crate feature unstable-enable only.

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

Creates a new NTTConvolution.

Note that this convolution will be able to compute convolutions whose output is of length <= n, where n is the largest power of two such that the given ring has a primitive n-th root of unity.

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(hom: H, allocator: A) -> Self

Creates a new NTTConvolution.

Note that this convolution will be able to compute convolutions whose output is of length <= n, where n is the largest power of two such that the domain of the given homomorphism has a primitive n-th root of unity.

Internally, twiddle factors for the underlying NTT will be stored as elements of the domain of the given homomorphism, while the convolutions are performed over the codomain. This can be used for more efficient NTTs, see e.g. zn_64::ZnFastmul.

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>

Returns the ring over which this object can compute convolutions.

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_main::Element], ring: S, )

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

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