Struct RNSConvolution

pub struct RNSConvolution<I = BigIntRing, C = NTTConvolution<Zn>, A = Global, CreateC = CreateNTTConvolution>
where
    I: RingStore + Clone,
    I::Type: IntegerRing,
    C: ConvolutionAlgorithm<ZnBase>,
    A: Allocator + Clone,
    CreateC: Fn(Zn) -> C,
{ /* private fields */ }

A ConvolutionAlgorithm that computes convolutions by computing them modulo a suitable composite modulus q, whose factors are of a certain shape, usually such as to allow for NTT-based convolutions.

Due to overlapping blanket impls, this type can only be used to compute convolutions over IntegerRings. For computing convolutions over ZnRings, wrap it in a RNSConvolutionZn.

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 RNSConvolution

pub fn new(max_log2_n: usize) -> Self

Creates a new RNSConvolution that can compute convolutions of sequences with output length <= 2^max_log2_n. As base convolution, the NTTConvolution is used.

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<I, C, A, CreateC> RNSConvolution<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C,

pub fn new_with( required_root_of_unity_log2: usize, max_prime_size_log2: usize, integer_ring: I, allocator: A, create_convolution: CreateC, ) -> Self

Creates a new RNSConvolution with all the given configuration parameters.

In particular

• required_root_of_unity_log2 and max_prime_size_log2 control which prime factors are used for the underlying composite modulus; Only primes <= 2^max_prime_size_log2 and = 1 mod required_root_of_unity_log2 are sampled
• integer_ring is the ring to store intermediate lifts in; this probably has to be BigIntRing, unless inputs are pretty small
• allocator is used to allocate elements modulo the internal modulus, as elements of zn_rns::Zn
• create_convolution is called whenever a new convolution algorithm for a new prime has to be created; the modulus of the given Zn always satisfies the constraints defined by max_prime_size_log2 and required_root_of_unity_log2

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, I, C, A, CreateC> ConvolutionAlgorithm<R> for RNSConvolution<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C, R: ?Sized + IntegerRing,

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

Elementwise adds the convolution of lhs and rhs to dst.

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

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

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

where F: PreparedConvolutionOperation<Self, R>,

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

impl<'a, I, C, A, CreateC> From<&'a RNSConvolution<I, C, A, CreateC>> for &'a RNSConvolutionZn<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C,

fn from(value: &'a RNSConvolution<I, C, A, CreateC>) -> Self

Converts to this type from the input type.

impl<'a, I, C, A, CreateC> From<&'a RNSConvolutionZn<I, C, A, CreateC>> for &'a RNSConvolution<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C,

fn from(value: &'a RNSConvolutionZn<I, C, A, CreateC>) -> Self

Converts to this type from the input type.

impl<I, C, A, CreateC> From<RNSConvolution<I, C, A, CreateC>> for RNSConvolutionZn<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C,

fn from(value: RNSConvolution<I, C, A, CreateC>) -> Self

Converts to this type from the input type.

impl<I, C, A, CreateC> From<RNSConvolutionZn<I, C, A, CreateC>> for RNSConvolution<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C,

fn from(value: RNSConvolutionZn<I, C, A, CreateC>) -> Self

Converts to this type from the input type.

impl<R, I, C, A, CreateC> PreparedConvolutionAlgorithm<R> for RNSConvolution<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: PreparedConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C, R: ?Sized + IntegerRing,

type PreparedConvolutionOperand = PreparedConvolutionOperand<R, C>

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

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

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

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

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

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

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

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

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

where S: RingStore<Type = R> + Copy, J: Iterator<Item = (&'a Self::PreparedConvolutionOperand, &'a Self::PreparedConvolutionOperand)>, Self::PreparedConvolutionOperand: 'a, Self: 'a, R: '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>,