qfall_math/integer_mod_q/poly_over_zq/arithmetic/
sub.rs

1// Copyright © 2023 Phil Milewski, Marcel Luca Schmidt
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//! Implementation of the [`Sub`] trait for [`PolyOverZq`] values.
10
11use super::super::PolyOverZq;
12use crate::{
13    error::MathError,
14    integer::PolyOverZ,
15    integer_mod_q::PolynomialRingZq,
16    macros::arithmetics::{
17        arithmetic_assign_trait_borrowed_to_owned, arithmetic_trait_borrowed_to_owned,
18        arithmetic_trait_mixed_borrowed_owned,
19    },
20    traits::CompareBase,
21};
22use flint_sys::{fmpz_mod_poly::fmpz_mod_poly_sub, fq::fq_sub};
23use std::{
24    ops::{Sub, SubAssign},
25    str::FromStr,
26};
27
28impl SubAssign<&PolyOverZq> for PolyOverZq {
29    /// Computes the subtraction of `self` and `other` reusing
30    /// the memory of `self`.
31    /// [`SubAssign`] can be used on [`PolyOverZq`] in combination with
32    /// [`PolyOverZq`] and [`PolyOverZ`].
33    ///
34    /// Parameters:
35    /// - `other`: specifies the polynomial to subtract from `self`
36    ///
37    /// Returns the difference of both polynomials modulo `q` as a [`PolyOverZq`].
38    ///
39    /// # Examples
40    /// ```
41    /// use qfall_math::{integer_mod_q::PolyOverZq, integer::PolyOverZ};
42    /// use std::str::FromStr;
43    ///
44    /// let mut a = PolyOverZq::from_str("3  1 2 3 mod 7").unwrap();
45    /// let b = PolyOverZq::from_str("5  1 2 -3 0 4 mod 7").unwrap();
46    /// let c = PolyOverZ::from_str("4  -1 2 5 3").unwrap();
47    ///
48    /// a -= &b;
49    /// a -= b;
50    /// a -= &c;
51    /// a -= c;
52    /// ```
53    ///
54    /// # Panics ...
55    /// - if the moduli of both [`PolyOverZq`] mismatch.
56    fn sub_assign(&mut self, other: &Self) {
57        if !self.compare_base(other) {
58            panic!("{}", self.call_compare_base_error(other).unwrap());
59        }
60
61        unsafe {
62            fmpz_mod_poly_sub(
63                &mut self.poly,
64                &self.poly,
65                &other.poly,
66                self.modulus.get_fmpz_mod_ctx_struct(),
67            )
68        };
69    }
70}
71impl SubAssign<&PolyOverZ> for PolyOverZq {
72    /// Documentation at [`PolyOverZq::sub_assign`].
73    fn sub_assign(&mut self, other: &PolyOverZ) {
74        let other = PolyOverZq::from((other, self.get_mod()));
75
76        self.sub_assign(&other);
77    }
78}
79
80arithmetic_assign_trait_borrowed_to_owned!(SubAssign, sub_assign, PolyOverZq, PolyOverZq);
81arithmetic_assign_trait_borrowed_to_owned!(SubAssign, sub_assign, PolyOverZq, PolyOverZ);
82
83impl Sub for &PolyOverZq {
84    type Output = PolyOverZq;
85    /// Implements the [`Sub`] trait for two [`PolyOverZq`] values.
86    /// [`Sub`] is implemented for any combination of [`PolyOverZq`] and borrowed [`PolyOverZq`].
87    ///
88    /// Parameters:
89    /// - `other`: specifies the polynomial to subtract from `self`
90    ///
91    /// Returns the result of the subtraction of both polynomials as a [`PolyOverZq`].
92    ///
93    /// # Examples
94    /// ```
95    /// use qfall_math::integer_mod_q::PolyOverZq;
96    /// use std::str::FromStr;
97    ///
98    /// let a: PolyOverZq = PolyOverZq::from_str("3  2 4 1 mod 7").unwrap();
99    /// let b: PolyOverZq = PolyOverZq::from_str("3  5 1 1 mod 7").unwrap();
100    ///
101    /// let c: PolyOverZq = &a - &b;
102    /// let d: PolyOverZq = a - b;
103    /// let e: PolyOverZq = &c - d;
104    /// let f: PolyOverZq = c - &e;
105    /// ```
106    ///
107    /// # Panics ...
108    /// - if the moduli of both [`PolyOverZq`] mismatch.
109    fn sub(self, other: Self) -> Self::Output {
110        self.sub_safe(other).unwrap()
111    }
112}
113
114arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZq, PolyOverZq, PolyOverZq);
115arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZq, PolyOverZq, PolyOverZq);
116
117impl Sub<&PolyOverZ> for &PolyOverZq {
118    type Output = PolyOverZq;
119    /// Implements the [`Sub`] trait for [`PolyOverZq`] and [`PolyOverZ`].
120    /// [`Sub`] is implemented for any combination of owned and borrowed values.
121    ///
122    /// Parameters:
123    /// - `other`: specifies the polynomial to subtract from `self`
124    ///
125    /// Returns the subtraction of both polynomials as a [`PolyOverZq`].
126    ///
127    /// # Examples
128    /// ```
129    /// use qfall_math::integer_mod_q::PolyOverZq;
130    /// use qfall_math::integer::PolyOverZ;
131    /// use std::str::FromStr;
132    ///
133    /// let a = PolyOverZq::from_str("4  -1 0 1 1 mod 17").unwrap();
134    /// let b = PolyOverZ::from_str("4  2 0 3 1").unwrap();
135    ///
136    /// let c: PolyOverZq = &a - &b;
137    /// ```
138    fn sub(self, other: &PolyOverZ) -> Self::Output {
139        let mut out = PolyOverZq::from(&self.modulus);
140        unsafe {
141            fmpz_mod_poly_sub(
142                &mut out.poly,
143                &self.poly,
144                &PolyOverZq::from((other, &self.modulus)).poly,
145                self.modulus.get_fmpz_mod_ctx_struct(),
146            );
147        }
148        out
149    }
150}
151
152arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZq, PolyOverZ, PolyOverZq);
153arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZq, PolyOverZ, PolyOverZq);
154
155impl Sub<&PolynomialRingZq> for &PolyOverZq {
156    type Output = PolynomialRingZq;
157    /// Implements the [`Sub`] trait for [`PolyOverZq`] and [`PolynomialRingZq`].
158    /// [`Sub`] is implemented for any combination of owned and borrowed values.
159    ///
160    /// Parameters:
161    /// - `other`: specifies the polynomial to subtract from `self`
162    ///
163    /// Returns the subtraction of both polynomials as a [`PolynomialRingZq`].
164    ///
165    /// # Examples
166    /// ```
167    /// use qfall_math::integer_mod_q::{PolyOverZq, PolynomialRingZq};
168    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
169    /// use qfall_math::integer::PolyOverZ;
170    /// use std::str::FromStr;
171    ///
172    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
173    /// let poly = PolyOverZ::from_str("4  -1 0 1 1").unwrap();
174    /// let a = PolynomialRingZq::from((&poly, &modulus));
175    /// let b = PolyOverZq::from_str("4  2 0 3 1 mod 17").unwrap();
176    ///
177    /// let c: PolynomialRingZq = &b - &a;
178    /// ```
179    ///
180    /// # Panics ...
181    /// - if the moduli mismatch.
182    fn sub(self, other: &PolynomialRingZq) -> Self::Output {
183        assert_eq!(
184            self.modulus,
185            other.modulus.get_q(),
186            "Tried to subtract polynomials with different moduli."
187        );
188
189        let mut out = PolynomialRingZq::from((&PolyOverZ::default(), &other.modulus));
190        unsafe {
191            fq_sub(
192                &mut out.poly.poly,
193                &self.get_representative_least_nonnegative_residue().poly,
194                &other.poly.poly,
195                other.modulus.get_fq_ctx(),
196            );
197        }
198        out
199    }
200}
201
202arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZq, PolynomialRingZq, PolynomialRingZq);
203arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZq, PolynomialRingZq, PolynomialRingZq);
204
205impl PolyOverZq {
206    /// Implements subtraction for two [`PolyOverZq`] values.
207    ///
208    /// Parameters:
209    /// - `other`: specifies the polynomial to subtract from `self`
210    ///
211    /// Returns the result of the subtraction of both polynomials as a [`PolyOverZq`] or an error if the moduli
212    /// mismatch.
213    ///
214    /// # Examples
215    /// ```
216    /// use qfall_math::integer_mod_q::PolyOverZq;
217    /// use std::str::FromStr;
218    ///
219    /// let a: PolyOverZq = PolyOverZq::from_str("3  2 4 1 mod 7").unwrap();
220    /// let b: PolyOverZq = PolyOverZq::from_str("3  5 1 1 mod 7").unwrap();
221    ///
222    /// let c: PolyOverZq = a.sub_safe(&b).unwrap();
223    /// ```
224    /// # Errors and Failures
225    /// - Returns a [`MathError`] of type [`MathError::MismatchingModulus`] if the moduli of
226    ///   both [`PolyOverZq`] mismatch.
227    pub fn sub_safe(&self, other: &Self) -> Result<PolyOverZq, MathError> {
228        if !self.compare_base(other) {
229            return Err(self.call_compare_base_error(other).unwrap());
230        }
231        let mut out = PolyOverZq::from_str(&format!("0 mod {}", self.modulus)).unwrap();
232        unsafe {
233            fmpz_mod_poly_sub(
234                &mut out.poly,
235                &self.poly,
236                &other.poly,
237                self.modulus.get_fmpz_mod_ctx_struct(),
238            );
239        }
240        Ok(out)
241    }
242}
243
244#[cfg(test)]
245mod test_sub_assign {
246    use super::PolyOverZq;
247    use crate::integer::PolyOverZ;
248    use std::str::FromStr;
249
250    /// Ensure that `sub_assign` works for small numbers.
251    #[test]
252    fn correct_small() {
253        let mut a = PolyOverZq::from_str("3  6 2 -3 mod 7").unwrap();
254        let b = PolyOverZq::from_str("5  -1 -2 -5 -1 -2 mod 7").unwrap();
255        let cmp = PolyOverZq::from_str("5  0 4 2 1 2 mod 7").unwrap();
256
257        a -= b;
258
259        assert_eq!(cmp, a);
260    }
261
262    /// Ensure that `sub_assign` works for large numbers.
263    #[test]
264    fn correct_large() {
265        let mut a = PolyOverZq::from_str(&format!(
266            "3  {} {} {} mod {}",
267            u32::MAX,
268            i32::MIN,
269            i32::MAX,
270            u64::MAX
271        ))
272        .unwrap();
273        let b = PolyOverZq::from_str(&format!("2  -{} -{} mod {}", u32::MAX, i32::MAX, u64::MAX))
274            .unwrap();
275        let cmp = PolyOverZq::from_str(&format!(
276            "3  {} -1 {} mod {}",
277            u64::from(u32::MAX) * 2,
278            i32::MAX,
279            u64::MAX
280        ))
281        .unwrap();
282
283        a -= b;
284
285        assert_eq!(cmp, a);
286    }
287
288    /// Ensure that `sub_assign` is available for all types.
289    #[test]
290    fn availability() {
291        let mut a = PolyOverZq::from_str("3  1 2 -3 mod 5").unwrap();
292        let b = PolyOverZq::from_str("3  -1 -2 3 mod 5").unwrap();
293        let c = PolyOverZ::from_str("2  -2 2").unwrap();
294
295        a -= &b;
296        a -= b;
297        a -= &c;
298        a -= c;
299    }
300
301    /// Ensures that mismatching moduli result in a panic.
302    #[test]
303    #[should_panic]
304    fn mismatching_moduli() {
305        let mut a: PolyOverZq = PolyOverZq::from_str("3  -5 4 1 mod 7").unwrap();
306        let b: PolyOverZq = PolyOverZq::from_str("3  -5 4 1 mod 8").unwrap();
307
308        a -= b;
309    }
310}
311
312#[cfg(test)]
313mod test_sub {
314    use super::PolyOverZq;
315    use std::str::FromStr;
316
317    /// Testing subtraction for two [`PolyOverZq`]
318    #[test]
319    fn sub() {
320        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
321        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
322        let c: PolyOverZq = a - b;
323        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
324    }
325
326    /// Testing subtraction for two borrowed [`PolyOverZq`]
327    #[test]
328    fn sub_borrow() {
329        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
330        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
331        let c: PolyOverZq = &a - &b;
332        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
333    }
334
335    /// Testing subtraction for borrowed [`PolyOverZq`] and [`PolyOverZq`]
336    #[test]
337    fn sub_first_borrowed() {
338        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
339        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
340        let c: PolyOverZq = a - b;
341        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
342    }
343
344    /// Testing subtraction for [`PolyOverZq`] and borrowed [`PolyOverZq`]
345    #[test]
346    fn sub_second_borrowed() {
347        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
348        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
349        let c: PolyOverZq = a - b;
350        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
351    }
352
353    /// Testing subtraction of [`PolyOverZq`] is reducing the polynomial
354    #[test]
355    fn sub_reduce() {
356        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 1 mod 7").unwrap();
357        let b: PolyOverZq = PolyOverZq::from_str("3  -5 4 -6 mod 7").unwrap();
358        let c: PolyOverZq = a - b;
359        assert_eq!(c, PolyOverZq::from_str("0 mod 7").unwrap());
360    }
361
362    /// Testing subtraction for large [`PolyOverZq`]
363    #[test]
364    fn sub_large_numbers() {
365        let a: PolyOverZq = PolyOverZq::from_str(&format!(
366            "3  -{} 4 {} mod {}",
367            u64::MAX,
368            i64::MIN,
369            u64::MAX - 58
370        ))
371        .unwrap();
372        let b: PolyOverZq = PolyOverZq::from_str(&format!(
373            "3  {} 5 {} mod {}",
374            i64::MIN,
375            i64::MIN,
376            u64::MAX - 58
377        ))
378        .unwrap();
379        let c: PolyOverZq = a - b;
380        assert_eq!(
381            c,
382            PolyOverZq::from_str(&format!(
383                "2  {} -1 mod {}",
384                i128::from(i64::MAX) - 57,
385                u64::MAX - 58
386            ))
387            .unwrap()
388        );
389    }
390
391    /// Testing subtraction for [`PolyOverZq`] with different moduli does not work
392    #[test]
393    #[should_panic]
394    fn sub_mismatching_modulus() {
395        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 9").unwrap();
396        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
397        let _c: PolyOverZq = a - b;
398    }
399
400    /// Testing whether sub_safe throws an error for mismatching moduli
401    #[test]
402    fn sub_safe_is_err() {
403        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 9").unwrap();
404        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
405        assert!(&a.sub_safe(&b).is_err());
406    }
407}
408
409#[cfg(test)]
410mod test_mul_poly_over_z {
411    use super::PolyOverZq;
412    use crate::integer::PolyOverZ;
413    use std::str::FromStr;
414
415    /// Checks if polynomial subtraction works fine for both borrowed
416    #[test]
417    fn borrowed_correctness() {
418        let poly_1 = PolyOverZq::from_str(&format!("1  {} mod {}", i64::MAX, u64::MAX)).unwrap();
419        let poly_2 = PolyOverZ::from_str("2  1 2").unwrap();
420        let poly_cmp =
421            PolyOverZq::from_str(&format!("2  {} -2 mod {}", i64::MAX as u64 - 1, u64::MAX))
422                .unwrap();
423
424        let poly_1 = &poly_1 - &poly_2;
425
426        assert_eq!(poly_cmp, poly_1);
427    }
428
429    /// Checks if subtraction works fine for different types
430    #[test]
431    fn availability() {
432        let poly = PolyOverZq::from_str("3  1 2 3 mod 17").unwrap();
433        let z = PolyOverZ::from(2);
434
435        _ = poly.clone() - z.clone();
436        _ = &poly - &z;
437        _ = &poly - z.clone();
438        _ = poly.clone() - &z;
439    }
440}
441
442#[cfg(test)]
443mod test_sub_poly_ring_zq {
444    use super::PolynomialRingZq;
445    use crate::integer_mod_q::PolyOverZq;
446    use std::str::FromStr;
447
448    /// Checks if polynomial subtraction works fine for both borrowed
449    #[test]
450    fn borrowed_correctness() {
451        let poly_1 =
452            PolynomialRingZq::from_str(&format!("2  2 {} / 4  1 2 3 4 mod {}", i64::MAX, u64::MAX))
453                .unwrap();
454        let poly_2 = PolynomialRingZq::from_str(&format!(
455            "2  -1 -{} / 4  1 2 3 4 mod {}",
456            i64::MAX as u64 - 2,
457            u64::MAX
458        ))
459        .unwrap();
460        let poly = PolyOverZq::from_str(&format!("2  1 2 mod {}", u64::MAX)).unwrap();
461
462        let poly_1 = &poly - &poly_1;
463
464        assert_eq!(poly_2, poly_1);
465    }
466
467    /// Checks if subtraction works fine for different types
468    #[test]
469    fn availability() {
470        let poly = PolynomialRingZq::from_str("3  1 2 3 / 4  1 2 3 4 mod 17").unwrap();
471        let zq = PolyOverZq::from((2, 17));
472
473        _ = zq.clone() - poly.clone();
474        _ = &zq - &poly;
475        _ = zq.clone() - &poly;
476        _ = &zq - poly.clone();
477    }
478
479    /// Checks if subtraction panics if the moduli mismatch
480    #[test]
481    #[should_panic]
482    fn different_moduli_panic() {
483        let poly = PolynomialRingZq::from_str("3  1 2 3 / 4  1 2 3 4 mod 17").unwrap();
484        let zq = PolyOverZq::from((2, 16));
485
486        _ = &zq - &poly;
487    }
488}
qfall_math/integer_mod_q/poly_over_zq/arithmetic/sub.rs

qfall_math/integer_mod_q/poly_over_zq/arithmetic/
sub.rs
