he_ring/rnsconv/
shared_lift.rs

1use std::alloc::Allocator;
2use std::alloc::Global;
3
4use feanor_math::matrix::*;
5use feanor_math::rings::zn::zn_64::*;
6use feanor_math::ring::*;
7use tracing::instrument;
8
9use super::RNSOperation;
10
11type UsedBaseConversion<A> = super::lift::AlmostExactBaseConversion<A>;
12
13///
14/// Computes almost exact base conversion with a shared factor.
15/// The exact map would be
16/// ```text
17///   Z/aqZ -> Z/aq'Z, x -> lift(x) mod aq'
18/// ```
19/// but as usual, we allow an error of `+/- aq`, unless the shortest 
20/// lift of the input is bounded by `aq/4`, in which case the result
21/// is always correct.
22/// 
23/// The functionality is exactly as for [`super::lift::AlmostExactBaseConversion`],
24/// except that it might be faster by reusing the shared factor `a`.
25/// 
26pub struct AlmostExactSharedBaseConversion<A = Global>
27    where A: Allocator + Clone
28{
29    conversion: UsedBaseConversion<A>,
30    out_moduli: Vec<Zn>
31}
32
33impl<A> AlmostExactSharedBaseConversion<A>
34    where A: Allocator + Clone
35{
36    ///
37    /// Creates a new [`AlmostExactSharedBaseConversion`], where
38    ///  - `a` is the product of `shared_moduli`
39    ///  - `q` is the product of `additional_in_moduli`
40    ///  - `a'` is the product of `additional_out_moduli`
41    /// 
42    /// The input resp. output moduli are ordered as in `shared_moduli`, followed
43    /// by `additional_in_moduli` resp. `additional_out_moduli`. In other words, the
44    /// additional moduli are appended at the end to the shared moduli.
45    /// 
46    #[instrument(skip_all)]
47    pub fn new_with(shared_moduli: Vec<Zn>, additional_in_moduli: Vec<Zn>, additional_out_moduli: Vec<Zn>, allocator: A) -> Self {
48        let in_moduli = shared_moduli.iter().cloned().chain(additional_in_moduli.into_iter()).collect::<Vec<_>>();
49        let out_moduli = shared_moduli.into_iter().chain(additional_out_moduli.iter().cloned()).collect::<Vec<_>>();
50        let conversion = UsedBaseConversion::new_with(in_moduli, additional_out_moduli, allocator);
51        Self {
52            out_moduli: out_moduli,
53            conversion: conversion
54        }
55    }
56
57    fn a_moduli_count(&self) -> usize {
58        self.out_moduli.len() - self.conversion.output_rings().len()
59    }
60}
61
62impl<A> RNSOperation for AlmostExactSharedBaseConversion<A>
63    where A: Allocator + Clone
64{
65    type Ring = Zn;
66    type RingType = ZnBase;
67
68    fn input_rings<'a>(&'a self) -> &'a [Self::Ring] {
69        self.conversion.input_rings()
70    }
71
72    fn output_rings<'a>(&'a self) -> &'a [Self::Ring] {
73        &self.out_moduli
74    }
75
76    #[instrument(skip_all)]
77    fn apply<V1, V2>(&self, input: Submatrix<V1, El<Self::Ring>>, mut output: SubmatrixMut<V2, El<Self::Ring>>)
78        where V1: AsPointerToSlice<El<Self::Ring>>,
79            V2: AsPointerToSlice<El<Self::Ring>>
80    {
81        assert_eq!(input.col_count(), output.col_count());
82        assert_eq!(input.row_count(), self.input_rings().len());
83        assert_eq!(output.row_count(), self.output_rings().len());
84
85        self.conversion.apply(input, output.reborrow().restrict_rows(self.a_moduli_count()..self.output_rings().len()));
86        for i in 0..self.a_moduli_count() {
87            for j in 0..input.col_count() {
88                *output.at_mut(i, j) = self.output_rings()[i].clone_el(input.at(i, j));
89            }
90        }
91    }
92}
93
94#[cfg(test)]
95use feanor_math::homomorphism::*;
96#[cfg(test)]
97use feanor_math::seq::*;
98
99#[test]
100fn test_rns_shared_base_conversion() {
101    let from = vec![Zn::new(17), Zn::new(97), Zn::new(113)];
102    let to = vec![Zn::new(17), Zn::new(97), Zn::new(113), Zn::new(257)];
103    let table = AlmostExactSharedBaseConversion::new_with(from.clone(), Vec::new(), vec![to[3]], Global);
104
105    for k in -(17 * 97 * 113 / 4)..=(17 * 97 * 113 / 4) {
106        let x = from.iter().map(|Zn| Zn.int_hom().map(k)).collect::<Vec<_>>();
107        let y = to.iter().map(|Zn| Zn.int_hom().map(k)).collect::<Vec<_>>();
108        let mut actual = to.iter().map(|Zn| Zn.int_hom().map(k)).collect::<Vec<_>>();
109
110        table.apply(
111            Submatrix::from_1d(&x, 3, 1), 
112            SubmatrixMut::from_1d(&mut actual, 4, 1)
113        );
114        
115        for i in 0..y.len() {
116            assert!(to[i].eq_el(&y[i], actual.at(i)));
117        }
118    }
119}
he_ring/rnsconv/shared_lift.rs

he_ring/rnsconv/
shared_lift.rs
