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