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