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