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;
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        let mut out = PolynomialRingZq::from((self, &other.modulus));
184        out -= other;
185        out
186    }
187}
188
189arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZq, PolynomialRingZq, PolynomialRingZq);
190arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZq, PolynomialRingZq, PolynomialRingZq);
191
192impl PolyOverZq {
193    /// Implements subtraction for two [`PolyOverZq`] values.
194    ///
195    /// Parameters:
196    /// - `other`: specifies the polynomial to subtract from `self`
197    ///
198    /// Returns the result of the subtraction of both polynomials as a [`PolyOverZq`] or an error if the moduli
199    /// mismatch.
200    ///
201    /// # Examples
202    /// ```
203    /// use qfall_math::integer_mod_q::PolyOverZq;
204    /// use std::str::FromStr;
205    ///
206    /// let a: PolyOverZq = PolyOverZq::from_str("3  2 4 1 mod 7").unwrap();
207    /// let b: PolyOverZq = PolyOverZq::from_str("3  5 1 1 mod 7").unwrap();
208    ///
209    /// let c: PolyOverZq = a.sub_safe(&b).unwrap();
210    /// ```
211    /// # Errors and Failures
212    /// - Returns a [`MathError`] of type [`MathError::MismatchingModulus`] if the moduli of
213    ///   both [`PolyOverZq`] mismatch.
214    pub fn sub_safe(&self, other: &Self) -> Result<PolyOverZq, MathError> {
215        if !self.compare_base(other) {
216            return Err(self.call_compare_base_error(other).unwrap());
217        }
218        let mut out = PolyOverZq::from_str(&format!("0 mod {}", self.modulus)).unwrap();
219        unsafe {
220            fmpz_mod_poly_sub(
221                &mut out.poly,
222                &self.poly,
223                &other.poly,
224                self.modulus.get_fmpz_mod_ctx_struct(),
225            );
226        }
227        Ok(out)
228    }
229}
230
231#[cfg(test)]
232mod test_sub_assign {
233    use super::PolyOverZq;
234    use crate::integer::PolyOverZ;
235    use std::str::FromStr;
236
237    /// Ensure that `sub_assign` works for small numbers.
238    #[test]
239    fn correct_small() {
240        let mut a = PolyOverZq::from_str("3  6 2 -3 mod 7").unwrap();
241        let b = PolyOverZq::from_str("5  -1 -2 -5 -1 -2 mod 7").unwrap();
242        let cmp = PolyOverZq::from_str("5  0 4 2 1 2 mod 7").unwrap();
243
244        a -= b;
245
246        assert_eq!(cmp, a);
247    }
248
249    /// Ensure that `sub_assign` works for large numbers.
250    #[test]
251    fn correct_large() {
252        let mut a = PolyOverZq::from_str(&format!(
253            "3  {} {} {} mod {}",
254            u32::MAX,
255            i32::MIN,
256            i32::MAX,
257            u64::MAX
258        ))
259        .unwrap();
260        let b = PolyOverZq::from_str(&format!("2  -{} -{} mod {}", u32::MAX, i32::MAX, u64::MAX))
261            .unwrap();
262        let cmp = PolyOverZq::from_str(&format!(
263            "3  {} -1 {} mod {}",
264            u64::from(u32::MAX) * 2,
265            i32::MAX,
266            u64::MAX
267        ))
268        .unwrap();
269
270        a -= b;
271
272        assert_eq!(cmp, a);
273    }
274
275    /// Ensure that `sub_assign` is available for all types.
276    #[test]
277    fn availability() {
278        let mut a = PolyOverZq::from_str("3  1 2 -3 mod 5").unwrap();
279        let b = PolyOverZq::from_str("3  -1 -2 3 mod 5").unwrap();
280        let c = PolyOverZ::from_str("2  -2 2").unwrap();
281
282        a -= &b;
283        a -= b;
284        a -= &c;
285        a -= c;
286    }
287
288    /// Ensures that mismatching moduli result in a panic.
289    #[test]
290    #[should_panic]
291    fn mismatching_moduli() {
292        let mut a: PolyOverZq = PolyOverZq::from_str("3  -5 4 1 mod 7").unwrap();
293        let b: PolyOverZq = PolyOverZq::from_str("3  -5 4 1 mod 8").unwrap();
294
295        a -= b;
296    }
297}
298
299#[cfg(test)]
300mod test_sub {
301    use super::PolyOverZq;
302    use std::str::FromStr;
303
304    /// Testing subtraction for two [`PolyOverZq`]
305    #[test]
306    fn sub() {
307        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
308        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
309        let c: PolyOverZq = a - b;
310        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
311    }
312
313    /// Testing subtraction for two borrowed [`PolyOverZq`]
314    #[test]
315    fn sub_borrow() {
316        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
317        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
318        let c: PolyOverZq = &a - &b;
319        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
320    }
321
322    /// Testing subtraction for borrowed [`PolyOverZq`] and [`PolyOverZq`]
323    #[test]
324    fn sub_first_borrowed() {
325        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
326        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
327        let c: PolyOverZq = a - b;
328        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
329    }
330
331    /// Testing subtraction for [`PolyOverZq`] and borrowed [`PolyOverZq`]
332    #[test]
333    fn sub_second_borrowed() {
334        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 7").unwrap();
335        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
336        let c: PolyOverZq = a - b;
337        assert_eq!(c, PolyOverZq::from_str("3  0 6 5 mod 7").unwrap());
338    }
339
340    /// Testing subtraction of [`PolyOverZq`] is reducing the polynomial
341    #[test]
342    fn sub_reduce() {
343        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 1 mod 7").unwrap();
344        let b: PolyOverZq = PolyOverZq::from_str("3  -5 4 -6 mod 7").unwrap();
345        let c: PolyOverZq = a - b;
346        assert_eq!(c, PolyOverZq::from_str("0 mod 7").unwrap());
347    }
348
349    /// Testing subtraction for large [`PolyOverZq`]
350    #[test]
351    fn sub_large_numbers() {
352        let a: PolyOverZq = PolyOverZq::from_str(&format!(
353            "3  -{} 4 {} mod {}",
354            u64::MAX,
355            i64::MIN,
356            u64::MAX - 58
357        ))
358        .unwrap();
359        let b: PolyOverZq = PolyOverZq::from_str(&format!(
360            "3  {} 5 {} mod {}",
361            i64::MIN,
362            i64::MIN,
363            u64::MAX - 58
364        ))
365        .unwrap();
366        let c: PolyOverZq = a - b;
367        assert_eq!(
368            c,
369            PolyOverZq::from_str(&format!(
370                "2  {} -1 mod {}",
371                i128::from(i64::MAX) - 57,
372                u64::MAX - 58
373            ))
374            .unwrap()
375        );
376    }
377
378    /// Testing subtraction for [`PolyOverZq`] with different moduli does not work
379    #[test]
380    #[should_panic]
381    fn sub_mismatching_modulus() {
382        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 9").unwrap();
383        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
384        let _c: PolyOverZq = a - b;
385    }
386
387    /// Testing whether sub_safe throws an error for mismatching moduli
388    #[test]
389    fn sub_safe_is_err() {
390        let a: PolyOverZq = PolyOverZq::from_str("3  2 4 6 mod 9").unwrap();
391        let b: PolyOverZq = PolyOverZq::from_str("3  -5 5 1 mod 7").unwrap();
392        assert!(&a.sub_safe(&b).is_err());
393    }
394}
395
396#[cfg(test)]
397mod test_mul_poly_over_z {
398    use super::PolyOverZq;
399    use crate::integer::PolyOverZ;
400    use std::str::FromStr;
401
402    /// Checks if polynomial subtraction works fine for both borrowed
403    #[test]
404    fn borrowed_correctness() {
405        let poly_1 = PolyOverZq::from_str(&format!("1  {} mod {}", i64::MAX, u64::MAX)).unwrap();
406        let poly_2 = PolyOverZ::from_str("2  1 2").unwrap();
407        let poly_cmp =
408            PolyOverZq::from_str(&format!("2  {} -2 mod {}", i64::MAX as u64 - 1, u64::MAX))
409                .unwrap();
410
411        let poly_1 = &poly_1 - &poly_2;
412
413        assert_eq!(poly_cmp, poly_1);
414    }
415
416    /// Checks if subtraction works fine for different types
417    #[test]
418    fn availability() {
419        let poly = PolyOverZq::from_str("3  1 2 3 mod 17").unwrap();
420        let z = PolyOverZ::from(2);
421
422        _ = poly.clone() - z.clone();
423        _ = &poly - &z;
424        _ = &poly - z.clone();
425        _ = poly.clone() - &z;
426    }
427}
428
429#[cfg(test)]
430mod test_sub_poly_ring_zq {
431    use super::PolynomialRingZq;
432    use crate::integer_mod_q::PolyOverZq;
433    use std::str::FromStr;
434
435    /// Checks if polynomial subtraction works fine for both borrowed
436    #[test]
437    fn borrowed_correctness() {
438        let poly_1 =
439            PolynomialRingZq::from_str(&format!("2  2 {} / 4  1 2 3 1 mod {}", i64::MAX, u64::MAX))
440                .unwrap();
441        let poly_2 = PolynomialRingZq::from_str(&format!(
442            "2  -1 -{} / 4  1 2 3 1 mod {}",
443            i64::MAX as u64 - 2,
444            u64::MAX
445        ))
446        .unwrap();
447        let poly = PolyOverZq::from_str(&format!("2  1 2 mod {}", u64::MAX)).unwrap();
448
449        let poly_1 = &poly - &poly_1;
450
451        assert_eq!(poly_2, poly_1);
452    }
453
454    /// Checks if subtraction works fine for different types
455    #[test]
456    fn availability() {
457        let poly = PolynomialRingZq::from_str("3  1 2 3 / 4  1 2 3 1 mod 17").unwrap();
458        let zq = PolyOverZq::from((2, 17));
459
460        _ = zq.clone() - poly.clone();
461        _ = &zq - &poly;
462        _ = zq.clone() - &poly;
463        _ = &zq - poly.clone();
464    }
465
466    /// Checks if subtraction panics if the moduli mismatch
467    #[test]
468    #[should_panic]
469    fn different_moduli_panic() {
470        let poly = PolynomialRingZq::from_str("3  1 2 3 / 4  1 2 3 4 mod 17").unwrap();
471        let zq = PolyOverZq::from((2, 16));
472
473        _ = &zq - &poly;
474    }
475}
qfall_math/integer_mod_q/poly_over_zq/arithmetic/sub.rs

qfall_math/integer_mod_q/poly_over_zq/arithmetic/
sub.rs
