1use crate::ring::RingRNS;
  2use crate::poly::PolyRNS;
  3use crate::modulus::barrett::Barrett;
  4use crate::scalar::ScalarRNS;
  5use crate::modulus::ONCE;
  6extern crate test;
  7
  8impl RingRNS<'_, u64>{
  9
 10    /// Updates b to floor(a / q[b.level()]).
 11    /// Expects a and b to be in the NTT domain.
 12    pub fn div_floor_by_last_modulus_ntt(&self, a: &PolyRNS<u64>, buf: &mut PolyRNS<u64>, b: &mut PolyRNS<u64>){
 13        assert!(b.level() >= a.level()-1, "invalid input b: b.level()={} < a.level()-1={}", b.level(), a.level()-1);
 14        let level = self.level();
 15        self.0[level].intt::<false>(a.at(level), buf.at_mut(0));
 16        let rescaling_constants: ScalarRNS<Barrett<u64>> = self.rescaling_constant();
 17        let (buf_ntt_q_scaling, buf_ntt_qi_scaling) = buf.0.split_at_mut(1);
 18        for (i, r) in self.0[0..level].iter().enumerate(){
 19            r.ntt::<false>(&buf_ntt_q_scaling[0], &mut buf_ntt_qi_scaling[0]);
 20            r.sum_aqqmb_prod_c_scalar_barrett::<ONCE>(&buf_ntt_qi_scaling[0], a.at(i), &rescaling_constants.0[i], b.at_mut(i));
 21        }
 22    }
 23
 24    /// Updates b to floor(b / q[b.level()]).
 25    /// Expects b to be in the NTT domain.
 26    pub fn div_floor_by_last_modulus_ntt_inplace(&self, buf: &mut PolyRNS<u64>, b: &mut PolyRNS<u64>){
 27        let level = self.level();
 28        self.0[level].intt::<true>(b.at(level), buf.at_mut(0));
 29        let rescaling_constants: ScalarRNS<Barrett<u64>> = self.rescaling_constant();
 30        let (buf_ntt_q_scaling, buf_ntt_qi_scaling) = buf.0.split_at_mut(1);
 31        for (i, r) in self.0[0..level].iter().enumerate(){
 32            r.ntt::<true>(&buf_ntt_q_scaling[0], &mut buf_ntt_qi_scaling[0]);
 33            r.sum_aqqmb_prod_c_scalar_barrett_inplace::<ONCE>(&buf_ntt_qi_scaling[0], &rescaling_constants.0[i], b.at_mut(i));
 34        }
 35    }
 36
 37    /// Updates b to floor(a / q[b.level()]).
 38    pub fn div_floor_by_last_modulus(&self, a: &PolyRNS<u64>, b: &mut PolyRNS<u64>){
 39        assert!(b.level() >= a.level()-1, "invalid input b: b.level()={} < a.level()-1={}", b.level(), a.level()-1);
 40        let level = self.level();
 41        let rescaling_constants:ScalarRNS<Barrett<u64>>  = self.rescaling_constant();
 42        for (i, r) in self.0[0..level].iter().enumerate(){
 43            r.sum_aqqmb_prod_c_scalar_barrett::<ONCE>(a.at(level), a.at(i), &rescaling_constants.0[i], b.at_mut(i));
 44        }
 45    }
 46
 47    /// Updates a to floor(b / q[b.level()]).
 48    pub fn div_floor_by_last_modulus_inplace(&self, a: &mut PolyRNS<u64>){
 49        let level = self.level();
 50        let rescaling_constants: ScalarRNS<Barrett<u64>> = self.rescaling_constant();
 51        let (a_i, a_level) = a.split_at_mut(level);
 52        for (i, r) in self.0[0..level].iter().enumerate(){
 53            r.sum_aqqmb_prod_c_scalar_barrett_inplace::<ONCE>(&a_level[0], &rescaling_constants.0[i], &mut a_i[i]);
 54        }
 55    }
 56
 57    pub fn div_floor_by_last_moduli(&self, nb_moduli:usize, a: &PolyRNS<u64>, b: &mut PolyRNS<u64>){
 58        if nb_moduli == 0{
 59            if a != b{
 60                b.copy(a);
 61            }
 62        }else{
 63            self.div_floor_by_last_modulus(a, b);
 64            (1..nb_moduli).for_each(|i|{self.at_level(self.level()-i).div_floor_by_last_modulus_inplace(b)});
 65        }
 66    }
 67
 68    pub fn div_floor_by_last_moduli_inplace(&self, nb_moduli:usize, a: &mut PolyRNS<u64>){
 69        (0..nb_moduli).for_each(|i|{self.at_level(self.level()-i).div_floor_by_last_modulus_inplace(a)});
 70    }
 71
 72    pub fn div_round_by_last_modulus_ntt(&self, a: &PolyRNS<u64>, buf: &mut PolyRNS<u64>, b: &mut PolyRNS<u64>){
 73        let level = self.level();
 74    }
 75}
 76
 77
 78#[cfg(test)]
 79mod tests {
 80    use num_bigint::BigInt;
 81    use num_bigint::Sign;
 82    use crate::ring::Ring;
 83    use crate::ring::impl_u64::ring_rns::new_rings;
 84    use sampling::source::Source;
 85    use super::*;
 86
 87    #[test]
 88    fn test_div_floor_by_last_modulus_ntt() {
 89        let n = 1<<10;
 90        let moduli: Vec<u64> = vec![0x1fffffffffc80001u64, 0x1fffffffffe00001u64];
 91        let rings: Vec<Ring<u64>> = new_rings(n, moduli);
 92        let ring_rns: RingRNS<'_, u64> = RingRNS::new(&rings);
 93        let seed: [u8; 32] = [0;32];
 94        let mut source: Source = Source::new(seed);
 95
 96        let mut a: PolyRNS<u64> = ring_rns.new_polyrns();
 97        let mut b: PolyRNS<u64> = ring_rns.new_polyrns();
 98        let mut c: PolyRNS<u64> = ring_rns.at_level(ring_rns.level()-1).new_polyrns();
 99
100        // Allocates a random PolyRNS
101        ring_rns.fill_uniform(&mut source, &mut a);
102
103        // Maps PolyRNS to [BigInt]
104        let mut coeffs_a: Vec<BigInt> = (0..n).map(|i|{BigInt::from(i)}).collect();
105        ring_rns.at_level(a.level()).to_bigint_inplace(&a, 1, &mut coeffs_a);
106
107        // Performs c = intt(ntt(a) / q_level)
108        ring_rns.ntt_inplace::<false>(&mut a);
109        ring_rns.div_floor_by_last_modulus_ntt(&a, &mut b, &mut c);
110        ring_rns.at_level(c.level()).intt_inplace::<false>(&mut c);
111
112        // Exports c to coeffs_c
113        let mut coeffs_c = vec![BigInt::from(0);c.n()];
114        ring_rns.at_level(c.level()).to_bigint_inplace(&c, 1, &mut coeffs_c);
115
116        // Performs floor division on a
117        let scalar_big = BigInt::from(ring_rns.0[ring_rns.level()].modulus.q);
118        coeffs_a.iter_mut().for_each(|a|{
119            // Emulates floor division in [0, q-1] and maps to [-(q-1)/2, (q-1)/2-1]
120            *a /= &scalar_big;
121            if a.sign() == Sign::Minus {
122                *a -= 1;
123            }
124        });
125
126    	assert!(coeffs_a == coeffs_c);
127    }
128}