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