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