1use math::poly::PolyRNS;
  2use math::ring::RingRNS;
  3use num_bigint::BigInt;
  4use num_bigint::Sign;
  5use sampling::source::Source;
  6
  7#[test]
  8fn rescaling_rns_u64() {
  9    let n = 1 << 10;
 10    let moduli: Vec<u64> = vec![0x1fffffffffc80001u64, 0x1fffffffffe00001u64, 0x1fffffffffb40001, 0x1fffffffff500001];
 11    let ring_rns: RingRNS<u64> = RingRNS::new(n, moduli);
 12
 13    test_div_floor_by_last_modulus::<false>(&ring_rns);
 14    test_div_floor_by_last_modulus::<true>(&ring_rns);
 15    test_div_floor_by_last_modulus_inplace::<false>(&ring_rns);
 16    test_div_floor_by_last_modulus_inplace::<true>(&ring_rns);
 17    test_div_floor_by_last_moduli::<false>(&ring_rns);
 18    test_div_floor_by_last_moduli::<true>(&ring_rns);
 19    test_div_floor_by_last_moduli_inplace::<false>(&ring_rns);
 20    test_div_floor_by_last_moduli_inplace::<true>(&ring_rns);
 21}
 22
 23fn test_div_floor_by_last_modulus<const NTT: bool>(ring_rns: &RingRNS<u64>) {
 24    let seed: [u8; 32] = [0; 32];
 25    let mut source: Source = Source::new(seed);
 26
 27    let mut a: PolyRNS<u64> = ring_rns.new_polyrns();
 28    let mut b: PolyRNS<u64> = ring_rns.new_polyrns();
 29    let mut c: PolyRNS<u64> = ring_rns.at_level(ring_rns.level() - 1).new_polyrns();
 30
 31    // Allocates a random PolyRNS
 32    ring_rns.fill_uniform(&mut source, &mut a);
 33
 34    // Maps PolyRNS to [BigInt]
 35    let mut coeffs_a: Vec<BigInt> = (0..a.n()).map(|i| BigInt::from(i)).collect();
 36    ring_rns
 37        .at_level(a.level())
 38        .to_bigint_inplace(&a, 1, &mut coeffs_a);
 39
 40    // Performs c = intt(ntt(a) / q_level)
 41    if NTT {
 42        ring_rns.ntt_inplace::<false>(&mut a);
 43    }
 44
 45    ring_rns.div_floor_by_last_modulus::<NTT>(&a, &mut b, &mut c);
 46
 47    if NTT {
 48        ring_rns.at_level(c.level()).intt_inplace::<false>(&mut c);
 49    }
 50
 51    // Exports c to coeffs_c
 52    let mut coeffs_c = vec![BigInt::from(0); c.n()];
 53    ring_rns
 54        .at_level(c.level())
 55        .to_bigint_inplace(&c, 1, &mut coeffs_c);
 56
 57    // Performs floor division on a
 58    let scalar_big = BigInt::from(ring_rns.0[ring_rns.level()].modulus.q);
 59    coeffs_a.iter_mut().for_each(|a| {
 60        // Emulates floor division in [0, q-1] and maps to [-(q-1)/2, (q-1)/2-1]
 61        *a /= &scalar_big;
 62        if a.sign() == Sign::Minus {
 63            *a -= 1;
 64        }
 65    });
 66
 67    assert!(coeffs_a == coeffs_c, "test_div_floor_by_last_modulus");
 68}
 69
 70fn test_div_floor_by_last_modulus_inplace<const NTT: bool>(ring_rns: &RingRNS<u64>) {
 71    let seed: [u8; 32] = [0; 32];
 72    let mut source: Source = Source::new(seed);
 73
 74    let mut a: PolyRNS<u64> = ring_rns.new_polyrns();
 75    let mut b: PolyRNS<u64> = ring_rns.new_polyrns();
 76
 77    // Allocates a random PolyRNS
 78    ring_rns.fill_uniform(&mut source, &mut a);
 79
 80    // Maps PolyRNS to [BigInt]
 81    let mut coeffs_a: Vec<BigInt> = (0..a.n()).map(|i| BigInt::from(i)).collect();
 82    ring_rns
 83        .at_level(a.level())
 84        .to_bigint_inplace(&a, 1, &mut coeffs_a);
 85
 86    // Performs c = intt(ntt(a) / q_level)
 87    if NTT {
 88        ring_rns.ntt_inplace::<false>(&mut a);
 89    }
 90
 91    ring_rns.div_floor_by_last_modulus_inplace::<NTT>(&mut b, &mut a);
 92
 93    if NTT {
 94        ring_rns.at_level(a.level()-1).intt_inplace::<false>(&mut a);
 95    }
 96
 97    // Exports c to coeffs_c
 98    let mut coeffs_c = vec![BigInt::from(0); a.n()];
 99    ring_rns
100        .at_level(a.level()-1)
101        .to_bigint_inplace(&a, 1, &mut coeffs_c);
102
103    // Performs floor division on a
104    let scalar_big = BigInt::from(ring_rns.0[ring_rns.level()].modulus.q);
105    coeffs_a.iter_mut().for_each(|a| {
106        // Emulates floor division in [0, q-1] and maps to [-(q-1)/2, (q-1)/2-1]
107        *a /= &scalar_big;
108        if a.sign() == Sign::Minus {
109            *a -= 1;
110        }
111    });
112
113    assert!(coeffs_a == coeffs_c, "test_div_floor_by_last_modulus_inplace");
114}
115
116fn test_div_floor_by_last_moduli<const NTT: bool>(ring_rns: &RingRNS<u64>) {
117    let seed: [u8; 32] = [0; 32];
118    let mut source: Source = Source::new(seed);
119
120    let nb_moduli: usize = ring_rns.level();
121
122    let mut a: PolyRNS<u64> = ring_rns.new_polyrns();
123    let mut b: PolyRNS<u64> = ring_rns.new_polyrns();
124    let mut c: PolyRNS<u64> = ring_rns.at_level(ring_rns.level() - nb_moduli).new_polyrns();
125
126    // Allocates a random PolyRNS
127    ring_rns.fill_uniform(&mut source, &mut a);
128
129    // Maps PolyRNS to [BigInt]
130    let mut coeffs_a: Vec<BigInt> = (0..a.n()).map(|i| BigInt::from(i)).collect();
131    ring_rns
132        .at_level(a.level())
133        .to_bigint_inplace(&a, 1, &mut coeffs_a);
134
135    // Performs c = intt(ntt(a) / q_level)
136    if NTT {
137        ring_rns.ntt_inplace::<false>(&mut a);
138    }
139
140    ring_rns.div_floor_by_last_moduli::<NTT>(nb_moduli, &a, &mut b, &mut c);
141
142    if NTT {
143        ring_rns.at_level(c.level()).intt_inplace::<false>(&mut c);
144    }
145
146    // Exports c to coeffs_c
147    let mut coeffs_c = vec![BigInt::from(0); c.n()];
148    ring_rns
149        .at_level(c.level())
150        .to_bigint_inplace(&c, 1, &mut coeffs_c);
151
152    // Performs floor division on a
153    let mut scalar_big = BigInt::from(1);
154    (0..nb_moduli).for_each(|i|{scalar_big *= BigInt::from(ring_rns.0[ring_rns.level()-i].modulus.q)});
155   
156    coeffs_a.iter_mut().for_each(|a| {
157        // Emulates floor division in [0, q-1] and maps to [-(q-1)/2, (q-1)/2-1]
158        *a /= &scalar_big;
159        if a.sign() == Sign::Minus {
160            *a -= 1;
161        }
162    });
163
164    assert!(coeffs_a == coeffs_c, "test_div_floor_by_last_moduli");
165}
166
167fn test_div_floor_by_last_moduli_inplace<const NTT: bool>(ring_rns: &RingRNS<u64>) {
168    let seed: [u8; 32] = [0; 32];
169    let mut source: Source = Source::new(seed);
170
171    let nb_moduli: usize = ring_rns.level();
172
173    let mut a: PolyRNS<u64> = ring_rns.new_polyrns();
174    let mut b: PolyRNS<u64> = ring_rns.new_polyrns();
175
176    // Allocates a random PolyRNS
177    ring_rns.fill_uniform(&mut source, &mut a);
178
179    // Maps PolyRNS to [BigInt]
180    let mut coeffs_a: Vec<BigInt> = (0..a.n()).map(|i| BigInt::from(i)).collect();
181    ring_rns
182        .at_level(a.level())
183        .to_bigint_inplace(&a, 1, &mut coeffs_a);
184
185    // Performs c = intt(ntt(a) / q_level)
186    if NTT {
187        ring_rns.ntt_inplace::<false>(&mut a);
188    }
189
190    ring_rns.div_floor_by_last_moduli_inplace::<NTT>(nb_moduli, &mut b, &mut a);
191
192    if NTT {
193        ring_rns.at_level(a.level()-nb_moduli).intt_inplace::<false>(&mut a);
194    }
195
196    // Exports c to coeffs_c
197    let mut coeffs_c = vec![BigInt::from(0); a.n()];
198    ring_rns
199        .at_level(a.level()-nb_moduli)
200        .to_bigint_inplace(&a, 1, &mut coeffs_c);
201
202    // Performs floor division on a
203    let mut scalar_big = BigInt::from(1);
204    (0..nb_moduli).for_each(|i|{scalar_big *= BigInt::from(ring_rns.0[ring_rns.level()-i].modulus.q)});
205    coeffs_a.iter_mut().for_each(|a| {
206        // Emulates floor division in [0, q-1] and maps to [-(q-1)/2, (q-1)/2-1]
207        *a /= &scalar_big;
208        if a.sign() == Sign::Minus {
209            *a -= 1;
210        }
211    });
212
213    assert!(coeffs_a == coeffs_c, "test_div_floor_by_last_moduli_inplace");
214}