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