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