Struct AlmostExactBaseConversion

pub struct AlmostExactBaseConversion<A = Global>
where
    A: Allocator + Clone,
{ /* private fields */ }

Stores values for an almost exact conversion between RNS bases. A complete conversion refers to the function

  Z/QZ -> Z/Q'Z, x -> [lift(x)]

In our case, the output of the function is allowed to have an error of { -Q, 0, Q }, unless the shortest lift of the input is bounded by Q/4, in which case the result is always correct.

Implementation

Implementation is changed to approximating the lifted value using lower precision integers, which can be used to determine the overflow when computing

  lift(x) = sum_q lift(x * q/Q mod q) * Q/q

modulo some q'.

Implementations

impl<A> AlmostExactBaseConversion<A>

where A: Allocator + Clone,

pub fn new_with(in_rings: Vec<Zn>, out_rings: Vec<Zn>, allocator: A) -> Self

Creates a new AlmostExactBaseConversion from q to q'. The moduli belonging to q' are expected to be sorted.

Trait Implementations

impl<A> RNSOperation for AlmostExactBaseConversion<A>

where A: Allocator + Clone,

fn apply<V1, V2>( &self, input: Submatrix<'_, V1, El<Self::Ring>>, output: SubmatrixMut<'_, V2, El<Self::Ring>>, )

where V1: AsPointerToSlice<El<Self::Ring>>, V2: AsPointerToSlice<El<Self::Ring>>,

Performs the (almost) exact RNS base conversion

  Z/QZ -> Z/Q'Z, x -> smallest_lift(x) + kQ mod Q''

where k in { -1, 0, 1 }.

Furthermore, if the shortest lift of the input is bounded by Q/4, then the result is guaranteed to be exact.

type Ring = RingValue<ZnBase>

type RingType = ZnBase

fn input_rings<'a>(&'a self) -> &'a [Zn]

fn output_rings<'a>(&'a self) -> &'a [Zn]