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