fhe-study/arith/src/ring_nq.rs
arith/src/ring_nq.rsRaw
1//! Polynomial ring Z_q[X]/(X^N+1)
2//!
3
4use anyhow::{anyhow, Result};
5use rand::{distributions::Distribution, Rng};
6use std::array;
7use std::fmt;
8use std::iter::Sum;
9use std::ops::{Add, AddAssign, Mul, Neg, Sub, SubAssign};
10
11use crate::ntt::NTT;
12use crate::zq::{modulus_u64, Zq};
13
14use crate::Ring;
15
16// NOTE: currently using fixed-size arrays, but pending to see if with
17// real-world parameters the stack can keep up; if not will move everything to
18// use Vec.
19/// PolynomialRing element, where the PolynomialRing is R = Z_q[X]/(X^n +1)
20/// The implementation assumes that q is prime.
21#[derive(Clone, Copy)]
22pub struct Rq<const Q: u64, const N: usize> {
23 pub(crate) coeffs: [Zq<Q>; N],
24
25 // evals are set when doig a PRxPR multiplication, so it can be reused in future
26 // multiplications avoiding recomputing it
27 pub(crate) evals: Option<[Zq<Q>; N]>,
28}
29
30impl<const Q: u64, const N: usize> Ring for Rq<Q, N> {
31 type C = Zq<Q>;
32
33 fn coeffs(&self) -> Vec<Self::C> {
34 self.coeffs.to_vec()
35 }
36 fn zero() -> Self {
37 let coeffs = array::from_fn(|_| Zq::zero());
38 Self {
39 coeffs,
40 evals: None,
41 }
42 }
43 fn rand(mut rng: impl Rng, dist: impl Distribution<f64>) -> Self {
44 // let coeffs: [Zq<Q>; N] = array::from_fn(|_| Zq::from_u64(dist.sample(&mut rng)));
45 let coeffs: [Zq<Q>; N] = array::from_fn(|_| Self::C::rand(&mut rng, &dist));
46 Self {
47 coeffs,
48 evals: None,
49 }
50 }
51
52 fn from_vec(coeffs: Vec<Zq<Q>>) -> Self {
53 let mut p = coeffs;
54 modulus::<Q, N>(&mut p);
55 let coeffs = array::from_fn(|i| p[i]);
56 Self {
57 coeffs,
58 evals: None,
59 }
60 }
61
62 // returns the decomposition of each polynomial coefficient, such
63 // decomposition will be a vecotor of length N, containint N vectors of Zq
64 fn decompose(&self, beta: u32, l: u32) -> Vec<Self> {
65 let elems: Vec<Vec<Zq<Q>>> = self.coeffs.iter().map(|r| r.decompose(beta, l)).collect();
66 // transpose it
67 let r: Vec<Vec<Zq<Q>>> = (0..elems[0].len())
68 .map(|i| (0..elems.len()).map(|j| elems[j][i]).collect())
69 .collect();
70 // convert it to Rq<Q,N>
71 r.iter().map(|a_i| Self::from_vec(a_i.clone())).collect()
72 }
73}
74
75impl<const Q: u64, const N: usize> From<crate::ring_n::R<N>> for Rq<Q, N> {
76 fn from(r: crate::ring_n::R<N>) -> Self {
77 Self::from_vec(
78 r.coeffs()
79 .iter()
80 .map(|e| Zq::<Q>::from_f64(*e as f64))
81 .collect(),
82 )
83 }
84}
85
86// apply mod (X^N+1)
87pub fn modulus<const Q: u64, const N: usize>(p: &mut Vec<Zq<Q>>) {
88 if p.len() < N {
89 return;
90 }
91 for i in N..p.len() {
92 p[i - N] = p[i - N].clone() - p[i].clone();
93 p[i] = Zq(0);
94 }
95 p.truncate(N);
96}
97
98// PR stands for PolynomialRing
99impl<const Q: u64, const N: usize> Rq<Q, N> {
100 pub fn coeffs(&self) -> [Zq<Q>; N] {
101 self.coeffs
102 }
103 pub fn compute_evals(&mut self) {
104 self.evals = Some(NTT::<Q, N>::ntt(self.coeffs));
105 }
106 pub fn to_r(self) -> crate::R<N> {
107 crate::R::<N>::from(self)
108 }
109
110 // TODO rm since it is implemented in Ring trait impl
111 // pub fn zero() -> Self {
112 // let coeffs = array::from_fn(|_| Zq::zero());
113 // Self {
114 // coeffs,
115 // evals: None,
116 // }
117 // }
118 // this method is mostly for tests
119 pub fn from_vec_u64(coeffs: Vec<u64>) -> Self {
120 let coeffs_mod_q = coeffs.iter().map(|c| Zq::from_u64(*c)).collect();
121 Self::from_vec(coeffs_mod_q)
122 }
123 pub fn from_vec_f64(coeffs: Vec<f64>) -> Self {
124 let coeffs_mod_q = coeffs.iter().map(|c| Zq::from_f64(*c)).collect();
125 Self::from_vec(coeffs_mod_q)
126 }
127 pub fn from_vec_i64(coeffs: Vec<i64>) -> Self {
128 let coeffs_mod_q = coeffs.iter().map(|c| Zq::from_f64(*c as f64)).collect();
129 Self::from_vec(coeffs_mod_q)
130 }
131 pub fn new(coeffs: [Zq<Q>; N], evals: Option<[Zq<Q>; N]>) -> Self {
132 Self { coeffs, evals }
133 }
134
135 pub fn rand_abs(mut rng: impl Rng, dist: impl Distribution<f64>) -> Result<Self> {
136 let coeffs: [Zq<Q>; N] = array::from_fn(|_| Zq::from_f64(dist.sample(&mut rng).abs()));
137 Ok(Self {
138 coeffs,
139 evals: None,
140 })
141 }
142 pub fn rand_f64_abs(mut rng: impl Rng, dist: impl Distribution<f64>) -> Result<Self> {
143 let coeffs: [Zq<Q>; N] = array::from_fn(|_| Zq::from_f64(dist.sample(&mut rng).abs()));
144 Ok(Self {
145 coeffs,
146 evals: None,
147 })
148 }
149 pub fn rand_f64(mut rng: impl Rng, dist: impl Distribution<f64>) -> Result<Self> {
150 let coeffs: [Zq<Q>; N] = array::from_fn(|_| Zq::from_f64(dist.sample(&mut rng)));
151 Ok(Self {
152 coeffs,
153 evals: None,
154 })
155 }
156 pub fn rand_u64(mut rng: impl Rng, dist: impl Distribution<u64>) -> Result<Self> {
157 let coeffs: [Zq<Q>; N] = array::from_fn(|_| Zq::from_u64(dist.sample(&mut rng)));
158 Ok(Self {
159 coeffs,
160 evals: None,
161 })
162 }
163 // WIP. returns random v \in {0,1}. // TODO {-1, 0, 1}
164 pub fn rand_bin(mut rng: impl Rng, dist: impl Distribution<bool>) -> Result<Self> {
165 let coeffs: [Zq<Q>; N] = array::from_fn(|_| Zq::from_bool(dist.sample(&mut rng)));
166 Ok(Rq {
167 coeffs,
168 evals: None,
169 })
170 }
171 // Warning: this method will behave differently depending on the values P and Q:
172 // if Q<P, it just 'renames' the modulus parameter to P
173 // if Q>=P, it crops to mod P
174 pub fn remodule<const P: u64>(&self) -> Rq<P, N> {
175 Rq::<P, N>::from_vec_u64(self.coeffs().iter().map(|m_i| m_i.0).collect())
176 }
177
178 /// perform the mod switch operation from Q to Q', where Q2=Q'
179 pub fn mod_switch<const Q2: u64>(&self) -> Rq<Q2, N> {
180 Rq::<Q2, N> {
181 coeffs: array::from_fn(|i| self.coeffs[i].mod_switch::<Q2>()),
182 evals: None,
183 }
184 }
185
186 // applies mod(T) to all coefficients of self
187 pub fn coeffs_mod<const T: u64>(&self) -> Self {
188 Rq::<Q, N>::from_vec_u64(
189 self.coeffs()
190 .iter()
191 .map(|m_i| modulus_u64::<T>(m_i.0))
192 .collect(),
193 )
194 }
195
196 // TODO review if needed, or if with this interface
197 pub fn mul_by_matrix(&self, m: &Vec<Vec<Zq<Q>>>) -> Result<Vec<Zq<Q>>> {
198 matrix_vec_product(m, &self.coeffs.to_vec())
199 }
200 pub fn mul_by_zq(&self, s: &Zq<Q>) -> Self {
201 Self {
202 coeffs: array::from_fn(|i| self.coeffs[i] * *s),
203 evals: None,
204 }
205 }
206 pub fn mul_by_u64(&self, s: u64) -> Self {
207 let s = Zq::from_u64(s);
208 Self {
209 coeffs: array::from_fn(|i| self.coeffs[i] * s),
210 // coeffs: self.coeffs.iter().map(|&e| e * s).collect(),
211 evals: None,
212 }
213 }
214 pub fn mul_by_f64(&self, s: f64) -> Self {
215 Self {
216 coeffs: array::from_fn(|i| Zq::from_f64(self.coeffs[i].0 as f64 * s)),
217 evals: None,
218 }
219 }
220
221 pub fn mul(&mut self, rhs: &mut Self) -> Self {
222 mul_mut(self, rhs)
223 }
224 // divides by the given scalar 's' and rounds, returning a Rq<Q,N>
225 // TODO rm
226 pub fn div_round(&self, s: u64) -> Self {
227 let r: Vec<f64> = self
228 .coeffs()
229 .iter()
230 .map(|e| (e.0 as f64 / s as f64).round())
231 .collect();
232 Rq::<Q, N>::from_vec_f64(r)
233 }
234 // returns [ [(num/den) * self].round() ] mod q
235 // ie. performs the multiplication and division over f64, and then it rounds the
236 // result, only applying the mod Q at the end
237 pub fn mul_div_round(&self, num: u64, den: u64) -> Self {
238 let r: Vec<f64> = self
239 .coeffs()
240 .iter()
241 .map(|e| ((num as f64 * e.0 as f64) / den as f64).round())
242 .collect();
243 Rq::<Q, N>::from_vec_f64(r)
244 }
245
246 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
247 // TODO simplify
248 let mut str = "";
249 let mut zero = true;
250 for (i, coeff) in self.coeffs.iter().enumerate().rev() {
251 if coeff.0 == 0 {
252 continue;
253 }
254 zero = false;
255 f.write_str(str)?;
256 if coeff.0 != 1 {
257 f.write_str(coeff.0.to_string().as_str())?;
258 if i > 0 {
259 f.write_str("*")?;
260 }
261 }
262 if coeff.0 == 1 && i == 0 {
263 f.write_str(coeff.0.to_string().as_str())?;
264 }
265 if i == 1 {
266 f.write_str("x")?;
267 } else if i > 1 {
268 f.write_str("x^")?;
269 f.write_str(i.to_string().as_str())?;
270 }
271 str = " + ";
272 }
273 if zero {
274 f.write_str("0")?;
275 }
276
277 f.write_str(" mod Z_")?;
278 f.write_str(Q.to_string().as_str())?;
279 f.write_str("/(X^")?;
280 f.write_str(N.to_string().as_str())?;
281 f.write_str("+1)")?;
282 Ok(())
283 }
284
285 pub fn infinity_norm(&self) -> u64 {
286 self.coeffs()
287 .iter()
288 .map(|x| if x.0 > (Q / 2) { Q - x.0 } else { x.0 })
289 .fold(0, |a, b| a.max(b))
290 }
291 pub fn mod_centered_q(&self) -> crate::ring_n::R<N> {
292 self.to_r().mod_centered_q::<Q>()
293 }
294}
295pub fn matrix_vec_product<const Q: u64>(m: &Vec<Vec<Zq<Q>>>, v: &Vec<Zq<Q>>) -> Result<Vec<Zq<Q>>> {
296 // assert_eq!(m.len(), m[0].len()); // TODO change to returning err
297 // assert_eq!(m.len(), v.len());
298 if m.len() != m[0].len() {
299 return Err(anyhow!("expected 'm' to be a square matrix"));
300 }
301 if m.len() != v.len() {
302 return Err(anyhow!(
303 "m.len: {} should be equal to v.len(): {}",
304 m.len(),
305 v.len(),
306 ));
307 }
308
309 Ok(m.iter()
310 .map(|row| {
311 row.iter()
312 .zip(v.iter())
313 .map(|(&row_i, &v_i)| row_i * v_i)
314 .sum()
315 })
316 .collect::<Vec<Zq<Q>>>())
317}
318pub fn transpose<const Q: u64>(m: &[Vec<Zq<Q>>]) -> Vec<Vec<Zq<Q>>> {
319 // TODO case when m[0].len()=0
320 // TODO non square matrix
321 let mut r: Vec<Vec<Zq<Q>>> = vec![vec![Zq(0); m[0].len()]; m.len()];
322 for (i, m_row) in m.iter().enumerate() {
323 for (j, m_ij) in m_row.iter().enumerate() {
324 r[j][i] = *m_ij;
325 }
326 }
327 r
328}
329
330impl<const Q: u64, const N: usize> PartialEq for Rq<Q, N> {
331 fn eq(&self, other: &Self) -> bool {
332 self.coeffs == other.coeffs
333 }
334}
335impl<const Q: u64, const N: usize> Add<Rq<Q, N>> for Rq<Q, N> {
336 type Output = Self;
337
338 fn add(self, rhs: Self) -> Self {
339 Self {
340 coeffs: array::from_fn(|i| self.coeffs[i] + rhs.coeffs[i]),
341 evals: None,
342 }
343 // Self {
344 // coeffs: self
345 // .coeffs
346 // .iter()
347 // .zip(rhs.coeffs)
348 // .map(|(a, b)| *a + b)
349 // .collect(),
350 // evals: None,
351 // }
352 // Self(r.iter_mut().map(|e| e.r#mod()).collect()) // TODO mod should happen auto in +
353 }
354}
355impl<const Q: u64, const N: usize> Add<&Rq<Q, N>> for &Rq<Q, N> {
356 type Output = Rq<Q, N>;
357
358 fn add(self, rhs: &Rq<Q, N>) -> Self::Output {
359 Rq {
360 coeffs: array::from_fn(|i| self.coeffs[i] + rhs.coeffs[i]),
361 evals: None,
362 }
363 }
364}
365impl<const Q: u64, const N: usize> AddAssign for Rq<Q, N> {
366 fn add_assign(&mut self, rhs: Self) {
367 for i in 0..N {
368 self.coeffs[i] += rhs.coeffs[i];
369 }
370 }
371}
372
373impl<const Q: u64, const N: usize> Sum<Rq<Q, N>> for Rq<Q, N> {
374 fn sum<I>(iter: I) -> Self
375 where
376 I: Iterator<Item = Self>,
377 {
378 let mut acc = Rq::<Q, N>::zero();
379 for e in iter {
380 acc += e;
381 }
382 acc
383 }
384}
385
386impl<const Q: u64, const N: usize> Sub<Rq<Q, N>> for Rq<Q, N> {
387 type Output = Self;
388
389 fn sub(self, rhs: Self) -> Self {
390 Self {
391 coeffs: array::from_fn(|i| self.coeffs[i] - rhs.coeffs[i]),
392 evals: None,
393 }
394 }
395}
396impl<const Q: u64, const N: usize> Sub<&Rq<Q, N>> for &Rq<Q, N> {
397 type Output = Rq<Q, N>;
398
399 fn sub(self, rhs: &Rq<Q, N>) -> Self::Output {
400 Rq {
401 coeffs: array::from_fn(|i| self.coeffs[i] - rhs.coeffs[i]),
402 evals: None,
403 }
404 }
405}
406impl<const Q: u64, const N: usize> SubAssign for Rq<Q, N> {
407 fn sub_assign(&mut self, rhs: Self) {
408 for i in 0..N {
409 self.coeffs[i] -= rhs.coeffs[i];
410 }
411 }
412}
413
414impl<const Q: u64, const N: usize> Mul<Rq<Q, N>> for Rq<Q, N> {
415 type Output = Self;
416
417 fn mul(self, rhs: Self) -> Self {
418 mul(&self, &rhs)
419 }
420}
421impl<const Q: u64, const N: usize> Mul<&Rq<Q, N>> for &Rq<Q, N> {
422 type Output = Rq<Q, N>;
423
424 fn mul(self, rhs: &Rq<Q, N>) -> Self::Output {
425 mul(self, rhs)
426 }
427}
428
429// mul by Zq element
430impl<const Q: u64, const N: usize> Mul<Zq<Q>> for Rq<Q, N> {
431 type Output = Self;
432
433 fn mul(self, s: Zq<Q>) -> Self {
434 self.mul_by_zq(&s)
435 }
436}
437impl<const Q: u64, const N: usize> Mul<&Zq<Q>> for &Rq<Q, N> {
438 type Output = Rq<Q, N>;
439
440 fn mul(self, s: &Zq<Q>) -> Self::Output {
441 self.mul_by_zq(s)
442 }
443}
444// mul by u64
445impl<const Q: u64, const N: usize> Mul<u64> for Rq<Q, N> {
446 type Output = Self;
447
448 fn mul(self, s: u64) -> Self {
449 self.mul_by_u64(s)
450 }
451}
452impl<const Q: u64, const N: usize> Mul<&u64> for &Rq<Q, N> {
453 type Output = Rq<Q, N>;
454
455 fn mul(self, s: &u64) -> Self::Output {
456 self.mul_by_u64(*s)
457 }
458}
459// mul by f64
460impl<const Q: u64, const N: usize> Mul<f64> for Rq<Q, N> {
461 type Output = Self;
462
463 fn mul(self, s: f64) -> Self {
464 self.mul_by_f64(s)
465 }
466}
467impl<const Q: u64, const N: usize> Mul<&f64> for &Rq<Q, N> {
468 type Output = Rq<Q, N>;
469
470 fn mul(self, s: &f64) -> Self::Output {
471 self.mul_by_f64(*s)
472 }
473}
474
475impl<const Q: u64, const N: usize> Neg for Rq<Q, N> {
476 type Output = Self;
477
478 fn neg(self) -> Self::Output {
479 Self {
480 coeffs: array::from_fn(|i| -self.coeffs[i]),
481 evals: None,
482 }
483 }
484}
485
486// note: this assumes that Q is prime
487fn mul_mut<const Q: u64, const N: usize>(lhs: &mut Rq<Q, N>, rhs: &mut Rq<Q, N>) -> Rq<Q, N> {
488 // reuse evaluations if already computed
489 if !lhs.evals.is_some() {
490 lhs.evals = Some(NTT::<Q, N>::ntt(lhs.coeffs));
491 };
492 if !rhs.evals.is_some() {
493 rhs.evals = Some(NTT::<Q, N>::ntt(rhs.coeffs));
494 };
495 let lhs_evals = lhs.evals.unwrap();
496 let rhs_evals = rhs.evals.unwrap();
497
498 let c_ntt: [Zq<Q>; N] = array::from_fn(|i| lhs_evals[i] * rhs_evals[i]);
499 let c = NTT::<Q, { N }>::intt(c_ntt);
500 Rq::new(c, Some(c_ntt))
501}
502// note: this assumes that Q is prime
503// TODO impl karatsuba for non-prime Q
504fn mul<const Q: u64, const N: usize>(lhs: &Rq<Q, N>, rhs: &Rq<Q, N>) -> Rq<Q, N> {
505 // reuse evaluations if already computed
506 let lhs_evals = if lhs.evals.is_some() {
507 lhs.evals.unwrap()
508 } else {
509 NTT::<Q, N>::ntt(lhs.coeffs)
510 };
511 let rhs_evals = if rhs.evals.is_some() {
512 rhs.evals.unwrap()
513 } else {
514 NTT::<Q, N>::ntt(rhs.coeffs)
515 };
516
517 let c_ntt: [Zq<Q>; N] = array::from_fn(|i| lhs_evals[i] * rhs_evals[i]);
518 let c = NTT::<Q, { N }>::intt(c_ntt);
519 Rq::new(c, Some(c_ntt))
520}
521
522impl<const Q: u64, const N: usize> fmt::Display for Rq<Q, N> {
523 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
524 self.fmt(f)?;
525 Ok(())
526 }
527}
528impl<const Q: u64, const N: usize> fmt::Debug for Rq<Q, N> {
529 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
530 self.fmt(f)?;
531 Ok(())
532 }
533}
534
535#[cfg(test)]
536mod tests {
537 use super::*;
538
539 #[test]
540 fn test_polynomial_ring() {
541 // the test values used are generated with SageMath
542 const Q: u64 = 7;
543 const N: usize = 3;
544
545 // p = 1x + 2x^2 + 3x^3 + 4 x^4 + 5 x^5 in R=Z_q[X]/(X^n +1)
546 let p = Rq::<Q, N>::from_vec_u64(vec![0u64, 1, 2, 3, 4, 5]);
547 assert_eq!(p.to_string(), "4*x^2 + 4*x + 4 mod Z_7/(X^3+1)");
548
549 // try with coefficients bigger than Q
550 let p = Rq::<Q, N>::from_vec_u64(vec![0u64, 1, Q + 2, 3, 4, 5]);
551 assert_eq!(p.to_string(), "4*x^2 + 4*x + 4 mod Z_7/(X^3+1)");
552
553 // try with other ring
554 let p = Rq::<7, 4>::from_vec_u64(vec![0u64, 1, 2, 3, 4, 5]);
555 assert_eq!(p.to_string(), "3*x^3 + 2*x^2 + 3*x + 3 mod Z_7/(X^4+1)");
556
557 let p = Rq::<Q, N>::from_vec_u64(vec![0u64, 0, 0, 0, 4, 5]);
558 assert_eq!(p.to_string(), "2*x^2 + 3*x mod Z_7/(X^3+1)");
559
560 let p = Rq::<Q, N>::from_vec_u64(vec![5u64, 4, 5, 2, 1, 0]);
561 assert_eq!(p.to_string(), "5*x^2 + 3*x + 3 mod Z_7/(X^3+1)");
562
563 let a = Rq::<Q, N>::from_vec_u64(vec![0u64, 1, 2, 3, 4, 5]);
564 assert_eq!(a.to_string(), "4*x^2 + 4*x + 4 mod Z_7/(X^3+1)");
565
566 let b = Rq::<Q, N>::from_vec_u64(vec![5u64, 4, 3, 2, 1, 0]);
567 assert_eq!(b.to_string(), "3*x^2 + 3*x + 3 mod Z_7/(X^3+1)");
568
569 // add
570 assert_eq!((a.clone() + b.clone()).to_string(), "0 mod Z_7/(X^3+1)");
571 assert_eq!((&a + &b).to_string(), "0 mod Z_7/(X^3+1)");
572 // assert_eq!((a.0.clone() + b.0.clone()).to_string(), "[0, 0, 0]"); // TODO
573
574 // sub
575 assert_eq!(
576 (a.clone() - b.clone()).to_string(),
577 "x^2 + x + 1 mod Z_7/(X^3+1)"
578 );
579 }
580
581 #[test]
582 fn test_mul() -> Result<()> {
583 const Q: u64 = 2u64.pow(16) + 1;
584 const N: usize = 4;
585
586 let a: [u64; N] = [1u64, 2, 3, 4];
587 let b: [u64; N] = [1u64, 2, 3, 4];
588 let c: [u64; N] = [65513, 65517, 65531, 20];
589 test_mul_opt::<Q, N>(a, b, c)?;
590
591 let a: [u64; N] = [0u64, 0, 0, 2];
592 let b: [u64; N] = [0u64, 0, 0, 2];
593 let c: [u64; N] = [0u64, 0, 65533, 0];
594 test_mul_opt::<Q, N>(a, b, c)?;
595
596 // TODO more testvectors
597
598 Ok(())
599 }
600 fn test_mul_opt<const Q: u64, const N: usize>(
601 a: [u64; N],
602 b: [u64; N],
603 expected_c: [u64; N],
604 ) -> Result<()> {
605 let a: [Zq<Q>; N] = array::from_fn(|i| Zq::from_u64(a[i]));
606 let mut a = Rq::new(a, None);
607 let b: [Zq<Q>; N] = array::from_fn(|i| Zq::from_u64(b[i]));
608 let mut b = Rq::new(b, None);
609 let expected_c: [Zq<Q>; N] = array::from_fn(|i| Zq::from_u64(expected_c[i]));
610 let expected_c = Rq::new(expected_c, None);
611
612 let c = mul_mut(&mut a, &mut b);
613 assert_eq!(c, expected_c);
614 Ok(())
615 }
616
617 #[test]
618 fn test_rq_decompose() -> Result<()> {
619 const Q: u64 = 16;
620 const N: usize = 4;
621 let beta = 4;
622 let l = 2;
623
624 let a = Rq::<Q, N>::from_vec_u64(vec![7u64, 14, 3, 6]);
625 let d = a.decompose(beta, l);
626
627 assert_eq!(
628 d[0].coeffs().to_vec(),
629 vec![1u64, 3, 0, 1]
630 .iter()
631 .map(|e| Zq::<Q>::from_u64(*e))
632 .collect::<Vec<_>>()
633 );
634 assert_eq!(
635 d[1].coeffs().to_vec(),
636 vec![3u64, 2, 3, 2]
637 .iter()
638 .map(|e| Zq::<Q>::from_u64(*e))
639 .collect::<Vec<_>>()
640 );
641 Ok(())
642 }
643}