qfall_math/integer_mod_q/polynomial_ring_zq/get.rs
1// Copyright 2023 Marcel Luca Schmidt, Marvin Beckmann
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! Implementations to get content of a [`PolynomialRingZq].
10
11use super::PolynomialRingZq;
12use crate::{
13 integer::{PolyOverZ, Z},
14 integer_mod_q::{ModulusPolynomialRingZq, Zq},
15 traits::{GetCoefficient, SetCoefficient},
16};
17use flint3_sys::{fmpz_poly_degree, fmpz_poly_get_coeff_fmpz};
18
19impl GetCoefficient<Zq> for PolynomialRingZq {
20 /// Returns the coefficient of a [`PolynomialRingZq`] as a [`Zq`].
21 ///
22 /// If an index is provided which exceeds the highest set coefficient, `0` is returned.
23 ///
24 /// Parameters:
25 /// - `index`: the index of the coefficient to get (has to be positive)
26 ///
27 /// Returns the coefficient as a [`Zq`], or a [`MathError`](crate::error::MathError) if the provided index
28 /// is negative and therefore invalid, or it does not fit into an [`i64`].
29 ///
30 /// # Examples
31 /// ```
32 /// use qfall_math::traits::*;
33 /// use qfall_math::integer_mod_q::{PolynomialRingZq, Zq};
34 /// use std::str::FromStr;
35 ///
36 /// let poly_ring = PolynomialRingZq::from_str("3 0 1 1 / 4 1 0 0 1 mod 17").unwrap();
37 ///
38 /// let coeff_0: Zq = poly_ring.get_coeff(0).unwrap();
39 /// let coeff_1: Zq = unsafe{ poly_ring.get_coeff_unchecked(1) };
40 /// let coeff_3: Zq = poly_ring.get_coeff(3).unwrap();
41 ///
42 /// assert_eq!(Zq::from((0, 17)), coeff_0);
43 /// assert_eq!(Zq::from((1, 17)), coeff_1);
44 /// assert_eq!(Zq::from((0, 17)), coeff_3);
45 /// ```
46 ///
47 /// # Safety
48 /// To use this function safely, make sure that the selected index
49 /// is greater or equal than `0`.
50 unsafe fn get_coeff_unchecked(&self, index: i64) -> Zq {
51 let mut out_z = Z::default();
52 unsafe { fmpz_poly_get_coeff_fmpz(&mut out_z.value, &self.poly.poly, index) }
53 Zq::from((out_z, &self.modulus.get_q()))
54 }
55}
56
57impl GetCoefficient<Z> for PolynomialRingZq {
58 /// Returns the coefficient of a [`PolynomialRingZq`] as a [`Z`].
59 ///
60 /// If an index is provided which exceeds the highest set coefficient, `0` is returned.
61 ///
62 /// Parameters:
63 /// - `index`: the index of the coefficient to get (has to be positive)
64 ///
65 /// Returns the coefficient as a [`Z`], or a [`MathError`](crate::error::MathError) if the provided index
66 /// is negative and therefore invalid, or it does not fit into an [`i64`].
67 ///
68 /// # Examples
69 /// ```
70 /// use qfall_math::traits::*;
71 /// use qfall_math::integer::{PolyOverZ, Z};
72 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
73 /// use std::str::FromStr;
74 ///
75 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
76 /// let poly = PolyOverZ::from_str("3 0 1 1").unwrap();
77 /// let poly_ring = PolynomialRingZq::from((&poly, &modulus));
78 ///
79 /// let coeff_0: Z = poly_ring.get_coeff(0).unwrap();
80 /// let coeff_1: Z = unsafe{ poly_ring.get_coeff_unchecked(1) };
81 /// let coeff_3: Z = poly_ring.get_coeff(3).unwrap();
82 ///
83 /// assert_eq!(Z::ZERO, coeff_0);
84 /// assert_eq!(Z::ONE, coeff_1);
85 /// assert_eq!(Z::ZERO, coeff_3);
86 /// ```
87 ///
88 /// # Safety
89 /// To use this function safely, make sure that the selected index
90 /// is greater or equal than `0`.
91 unsafe fn get_coeff_unchecked(&self, index: i64) -> Z {
92 let mut out = Z::default();
93 unsafe { fmpz_poly_get_coeff_fmpz(&mut out.value, &self.poly.poly, index) }
94 out
95 }
96}
97
98impl PolynomialRingZq {
99 /// Returns the modulus object of the [`PolynomialRingZq`] element.
100 ///
101 /// # Examples
102 /// ```
103 /// use qfall_math::integer::PolyOverZ;
104 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
105 /// use std::str::FromStr;
106 ///
107 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
108 /// let poly = PolyOverZ::from_str("4 -1 0 1 1").unwrap();
109 /// let poly_ring = PolynomialRingZq::from((&poly, &modulus));
110 ///
111 /// let poly_ring_mod = poly_ring.get_mod();
112 ///
113 /// assert_eq!(modulus, poly_ring_mod);
114 /// ```
115 pub fn get_mod(&self) -> ModulusPolynomialRingZq {
116 self.modulus.clone()
117 }
118
119 /// Returns a representative polynomial of the [`PolynomialRingZq`] element with coefficients centered around `0`.
120 ///
121 /// The output [`PolyOverZ`] has coefficients in the range `(-⌈modulus/2⌉, ⌊modulus/2⌋]`,
122 /// i.e. `[-(modulus-1)/2, (modulus-1)/2]` for odd moduli and `(-modulus/2, modulus/2]` for even moduli.
123 /// Hence, the positive representative is chosen for the element `modulus/2` of even moduli.
124 /// Use [`PolynomialRingZq::get_representative_least_nonnegative_residue`] if they should be
125 /// in the range `[0, modulus)`.
126 ///
127 /// # Examples
128 /// ```
129 /// use qfall_math::integer_mod_q::PolynomialRingZq;
130 /// use qfall_math::integer::PolyOverZ;
131 /// use std::str::FromStr;
132 ///
133 /// let value = PolynomialRingZq::from_str("2 10 11 / 4 1 0 0 1 mod 21").unwrap();
134 ///
135 /// let least_abs_residue = value.get_representative_least_absolute_residue();
136 ///
137 /// assert_eq!(PolyOverZ::from_str("2 10 -10").unwrap(), least_abs_residue);
138 /// ```
139 pub fn get_representative_least_absolute_residue(&self) -> PolyOverZ {
140 let mut out = PolyOverZ::default();
141 for i in 0..=self.get_degree() {
142 let coeff: Zq = unsafe { self.get_coeff_unchecked(i) };
143 let lar_coeff = coeff.get_representative_least_absolute_residue();
144 unsafe { out.set_coeff_unchecked(i, lar_coeff) };
145 }
146 out
147 }
148
149 /// Returns a representative polynomial of the [`PolynomialRingZq`] element.
150 ///
151 /// The representation of the coefficients is in the range `[0, modulus)` and
152 /// the representation of the polynomial is in the range `[0, modulus_polynomial)`.
153 /// Use [`PolynomialRingZq::get_representative_least_absolute_residue`] if they should be
154 /// in the range `(-⌈modulus/2⌉, ⌊modulus/2⌋]`.
155 ///
156 /// # Examples
157 /// ```
158 /// use qfall_math::integer::PolyOverZ;
159 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
160 /// use std::str::FromStr;
161 ///
162 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
163 /// let poly = PolyOverZ::from_str("4 -1 0 1 1").unwrap();
164 /// let poly_ring = PolynomialRingZq::from((&poly, &modulus));
165 ///
166 /// let poly_z = poly_ring.get_representative_least_nonnegative_residue();
167 ///
168 /// let cmp_poly = PolyOverZ::from_str("3 15 0 1").unwrap();
169 /// assert_eq!(cmp_poly, poly_z);
170 /// ```
171 pub fn get_representative_least_nonnegative_residue(&self) -> PolyOverZ {
172 self.poly.clone()
173 }
174
175 /// Returns the degree of a [`PolynomialRingZq`] as a [`i64`].
176 /// The zero polynomial has degree `-1`.
177 ///
178 /// # Examples
179 /// ```
180 /// use qfall_math::integer::PolyOverZ;
181 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
182 /// use std::str::FromStr;
183 ///
184 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
185 /// let poly = PolyOverZ::from_str("3 0 1 1").unwrap();
186 /// let poly_ring = PolynomialRingZq::from((&poly, &modulus));
187 ///
188 /// let degree = poly_ring.get_degree();
189 ///
190 /// assert_eq!(2, degree);
191 /// ```
192 pub fn get_degree(&self) -> i64 {
193 unsafe { fmpz_poly_degree(&self.poly.poly) }
194 }
195}
196
197#[cfg(test)]
198mod test_get_coeff {
199 use crate::{
200 integer::{PolyOverZ, Z},
201 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq, Zq},
202 traits::GetCoefficient,
203 };
204 use std::str::FromStr;
205
206 /// Ensure that 0 is returned if the provided index is not yet set.
207 #[test]
208 fn index_out_of_range() {
209 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
210 let poly = PolyOverZ::from_str("3 1 1 1").unwrap();
211 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
212
213 let zero_coeff_z: Z = poly_ring.get_coeff(3).unwrap();
214 let zero_coeff_zq = poly_ring.get_coeff(3).unwrap();
215
216 assert_eq!(0, zero_coeff_z);
217 assert_eq!(Zq::from((0, 17)), zero_coeff_zq);
218 }
219
220 /// Tests if coefficients are returned correctly.
221 #[test]
222 fn coeff_correct() {
223 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
224 let poly = PolyOverZ::from_str("3 1 0 3").unwrap();
225 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
226
227 let coeff_z: Z = poly_ring.get_coeff(2).unwrap();
228 let coeff_zq = poly_ring.get_coeff(2).unwrap();
229
230 assert_eq!(3, coeff_z);
231 assert_eq!(Zq::from((3, 17)), coeff_zq);
232 }
233
234 /// Tests if large coefficients are returned correctly.
235 #[test]
236 fn large_coeff() {
237 let modulus =
238 ModulusPolynomialRingZq::from_str(&format!("5 1 0 4 1 1 mod {}", u64::MAX)).unwrap();
239 let poly = PolyOverZ::from_str(&format!("3 0 {} 1", i64::MAX)).unwrap();
240 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
241
242 let coefficient_1: Z = poly_ring.get_coeff(1).unwrap();
243 let coefficient_2: Zq = poly_ring.get_coeff(1).unwrap();
244
245 assert_eq!(i64::MAX, coefficient_1);
246 assert_eq!(Zq::from((i64::MAX, u64::MAX)), coefficient_2);
247 }
248
249 /// Tests if negative index yields an error in get_coeff with [`Z`].
250 #[test]
251 #[should_panic]
252 fn negative_index_error_z() {
253 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
254 let poly = PolyOverZ::from_str("3 1 0 3").unwrap();
255 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
256
257 let _: Z = poly_ring.get_coeff(-1).unwrap();
258 }
259
260 /// Tests if negative index yields an error in get_coeff with [`Zq`].
261 #[test]
262 #[should_panic]
263 fn negative_index_error_zq() {
264 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
265 let poly = PolyOverZ::from_str("3 1 0 3").unwrap();
266 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
267
268 let _: Zq = poly_ring.get_coeff(-1).unwrap();
269 }
270}
271
272#[cfg(test)]
273mod test_get_mod {
274 use crate::{
275 integer::PolyOverZ,
276 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
277 };
278 use std::str::FromStr;
279
280 /// Ensure that the large modulus polynomial is returned correctly.
281 #[test]
282 fn large_positive() {
283 let modulus =
284 ModulusPolynomialRingZq::from_str(&format!("4 1 0 0 1 mod {}", u64::MAX - 58))
285 .unwrap();
286 let poly = PolyOverZ::from_str("4 -1 0 1 1").unwrap();
287 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
288
289 assert_eq!(modulus, poly_ring.get_mod());
290 }
291}
292
293#[cfg(test)]
294mod test_get_representative_least_absolute_residue {
295 use crate::{integer::PolyOverZ, integer_mod_q::PolynomialRingZq};
296 use std::str::FromStr;
297
298 /// Check whether `get_representative_least_absolute_residue` outputs the correct value for large values
299 #[test]
300 fn large_numbers() {
301 let poly_ring = PolynomialRingZq::from_str(&format!(
302 "2 {} {} / 4 1 0 0 1 mod {}",
303 i64::MAX,
304 u64::MAX - 1,
305 u64::MAX
306 ))
307 .unwrap();
308
309 let poly_z = poly_ring.get_representative_least_absolute_residue();
310
311 let cmp_poly = PolyOverZ::from_str(&format!("2 {} -1", i64::MAX)).unwrap();
312 assert_eq!(cmp_poly, poly_z);
313 }
314
315 /// Check whether `get_representative_least_absolute_residue` outputs the correct value for special cases
316 #[test]
317 fn special_numbers() {
318 let poly_ring = PolynomialRingZq::from_str("3 10 0 11 / 4 1 0 0 1 mod 21").unwrap();
319
320 let poly_z = poly_ring.get_representative_least_absolute_residue();
321
322 let cmp_poly = PolyOverZ::from_str("3 10 0 -10").unwrap();
323 assert_eq!(cmp_poly, poly_z);
324 }
325
326 /// Returns the coefficients `0, 1, ..., modulus - 1` and their representatives
327 /// according to `mod±` as defined in FIPS 204 as strings.
328 fn coefficients_and_representatives(modulus: i64) -> (String, String) {
329 let coefficients: Vec<String> = (0..modulus).map(|value| value.to_string()).collect();
330 let representatives: Vec<String> = (0..modulus)
331 .map(|value| {
332 if value > modulus / 2 {
333 value - modulus
334 } else {
335 value
336 }
337 .to_string()
338 })
339 .collect();
340 (coefficients.join(" "), representatives.join(" "))
341 }
342
343 /// Checks whether every coefficient is mapped into `(-⌈modulus/2⌉, ⌊modulus/2⌋]`
344 /// for an odd and an even modulus, i.e. `modulus/2` is mapped to the positive representative.
345 #[test]
346 fn full_range() {
347 for modulus in [10, 11] {
348 let (coefficients, representatives) = coefficients_and_representatives(modulus);
349 // modulus polynomial `X^modulus + 1` s.t. no coefficient is reduced
350 let poly_ring = PolynomialRingZq::from_str(&format!(
351 "{modulus} {coefficients} / {} 1 {}1 mod {modulus}",
352 modulus + 1,
353 "0 ".repeat(modulus as usize - 1)
354 ))
355 .unwrap();
356
357 let poly_z = poly_ring.get_representative_least_absolute_residue();
358
359 let cmp_poly = PolyOverZ::from_str(&format!("{modulus} {representatives}")).unwrap();
360 assert_eq!(cmp_poly, poly_z);
361 }
362 }
363}
364
365#[cfg(test)]
366mod test_get_representative_least_nonnegative_residue {
367 use crate::{
368 integer::PolyOverZ,
369 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
370 };
371 use std::str::FromStr;
372
373 /// Ensure that the getter works for large entries.
374 #[test]
375 fn large_positive() {
376 let large_prime = u64::MAX - 58;
377 let modulus =
378 ModulusPolynomialRingZq::from_str(&format!("4 1 0 0 1 mod {large_prime}")).unwrap();
379 let poly = PolyOverZ::from_str("4 -1 0 1 1").unwrap();
380 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
381
382 let poly_z = poly_ring.get_representative_least_nonnegative_residue();
383
384 let cmp_poly = PolyOverZ::from_str(&format!("3 {} 0 1", u64::MAX - 60)).unwrap();
385 assert_eq!(cmp_poly, poly_z);
386 }
387}
388
389#[cfg(test)]
390mod test_get_degree {
391 use crate::{
392 integer::PolyOverZ,
393 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
394 };
395 use std::str::FromStr;
396
397 /// Ensure that degree is working.
398 #[test]
399 fn degree() {
400 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
401 let poly = PolyOverZ::from_str("3 0 1 1").unwrap();
402 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
403
404 let deg = poly_ring.get_degree();
405
406 assert_eq!(2, deg);
407 }
408
409 /// Ensure that degree is working for constant polynomials.
410 #[test]
411 fn degree_constant() {
412 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
413 let poly = PolyOverZ::from(1);
414 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
415
416 let deg = poly_ring.get_degree();
417
418 assert_eq!(0, deg);
419 }
420
421 /// Ensure that degree is working for polynomials with leading 0 coefficients.
422 #[test]
423 fn degree_leading_zeros() {
424 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
425 let poly = PolyOverZ::from_str("3 1 0 0").unwrap();
426 let poly_ring = PolynomialRingZq::from((&poly, &modulus));
427
428 let deg = poly_ring.get_degree();
429
430 assert_eq!(0, deg);
431 }
432}