qfall_math/integer/poly_over_z/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 [`PolyOverZ`] values.
10
11use super::super::PolyOverZ;
12use crate::{
13    integer_mod_q::{PolyOverZq, PolynomialRingZq},
14    macros::arithmetics::{
15        arithmetic_assign_trait_borrowed_to_owned, arithmetic_trait_borrowed_to_owned,
16        arithmetic_trait_mixed_borrowed_owned,
17    },
18    rational::PolyOverQ,
19};
20use flint_sys::{
21    fmpq_poly::fmpq_poly_sub, fmpz_mod_poly::fmpz_mod_poly_sub, fmpz_poly::fmpz_poly_sub,
22    fq::fq_sub,
23};
24use std::ops::{Sub, SubAssign};
25
26impl SubAssign<&PolyOverZ> for PolyOverZ {
27    /// Computes the subtraction of `self` and `other` reusing
28    /// the memory of `self`.
29    ///
30    /// Parameters:
31    /// - `other`: specifies the polynomial to subtract from `self`
32    ///
33    /// Returns the difference of both polynomials as a [`PolyOverZ`].
34    ///
35    /// # Examples
36    /// ```
37    /// use qfall_math::integer::PolyOverZ;
38    /// use std::str::FromStr;
39    ///
40    /// let mut a = PolyOverZ::from_str("3  1 2 -3").unwrap();
41    /// let b = PolyOverZ::from_str("5  1 2 -3 0 8").unwrap();
42    ///
43    /// a -= &b;
44    /// a -= b;
45    /// ```
46    fn sub_assign(&mut self, other: &Self) {
47        unsafe { fmpz_poly_sub(&mut self.poly, &self.poly, &other.poly) };
48    }
49}
50
51arithmetic_assign_trait_borrowed_to_owned!(SubAssign, sub_assign, PolyOverZ, PolyOverZ);
52
53impl Sub for &PolyOverZ {
54    type Output = PolyOverZ;
55    /// Implements the [`Sub`] trait for two [`PolyOverZ`] values.
56    /// [`Sub`] is implemented for any combination of [`PolyOverZ`] and borrowed [`PolyOverZ`].
57    ///
58    /// Parameters:
59    /// - `other`: specifies the value to subtract from `self`
60    ///
61    /// Returns the result of the subtraction of both polynomials as a [`PolyOverZ`].
62    ///
63    /// # Examples
64    /// ```
65    /// use qfall_math::integer::PolyOverZ;
66    /// use std::str::FromStr;
67    ///
68    /// let a: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
69    /// let b: PolyOverZ = PolyOverZ::from_str("5  1 2 -3 0 8").unwrap();
70    ///
71    /// let c: PolyOverZ = &a - &b;
72    /// let d: PolyOverZ = a - b;
73    /// let e: PolyOverZ = &c - d;
74    /// let f: PolyOverZ = c - &e;
75    /// ```
76    fn sub(self, other: Self) -> Self::Output {
77        let mut out = PolyOverZ::default();
78        unsafe {
79            fmpz_poly_sub(&mut out.poly, &self.poly, &other.poly);
80        }
81        out
82    }
83}
84
85arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZ, PolyOverZ, PolyOverZ);
86arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZ, PolyOverZ, PolyOverZ);
87
88impl Sub<&PolyOverZq> for &PolyOverZ {
89    type Output = PolyOverZq;
90    /// Implements the [`Sub`] trait for [`PolyOverZ`] and [`PolyOverZq`].
91    /// [`Sub`] is implemented for any combination of owned and borrowed values.
92    ///
93    /// Parameters:
94    /// - `other`: specifies the polynomial to subtract from `self`
95    ///
96    /// Returns the subtraction of both polynomials as a [`PolyOverZq`].
97    ///
98    /// # Examples
99    /// ```
100    /// use qfall_math::integer_mod_q::PolyOverZq;
101    /// use qfall_math::integer::PolyOverZ;
102    /// use std::str::FromStr;
103    ///
104    /// let a = PolyOverZ::from_str("4  2 0 3 1").unwrap();
105    /// let b = PolyOverZq::from_str("4  -1 0 1 1 mod 17").unwrap();
106    ///
107    /// let c: PolyOverZq = &a - &b;
108    /// ```
109    fn sub(self, other: &PolyOverZq) -> Self::Output {
110        let mut out = PolyOverZq::from(&other.modulus);
111        unsafe {
112            fmpz_mod_poly_sub(
113                &mut out.poly,
114                &PolyOverZq::from((self, &other.modulus)).poly,
115                &other.poly,
116                other.modulus.get_fmpz_mod_ctx_struct(),
117            );
118        }
119        out
120    }
121}
122
123arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZ, PolyOverZq, PolyOverZq);
124arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZ, PolyOverZq, PolyOverZq);
125
126impl Sub<&PolynomialRingZq> for &PolyOverZ {
127    type Output = PolynomialRingZq;
128    /// Implements the [`Sub`] trait for [`PolyOverZ`] and [`PolynomialRingZq`].
129    /// [`Sub`] is implemented for any combination of owned and borrowed values.
130    ///
131    /// Parameters:
132    /// - `other`: specifies the polynomial to subtract from `self`
133    ///
134    /// Returns the subtraction of both polynomials as a [`PolynomialRingZq`].
135    ///
136    /// # Examples
137    /// ```
138    /// use qfall_math::integer_mod_q::PolynomialRingZq;
139    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
140    /// use qfall_math::integer::PolyOverZ;
141    /// use std::str::FromStr;
142    ///
143    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
144    /// let poly = PolyOverZ::from_str("4  -1 0 1 1").unwrap();
145    /// let a = PolynomialRingZq::from((&poly, &modulus));
146    /// let b = PolyOverZ::from_str("4  2 0 3 1").unwrap();
147    ///
148    /// let c: PolynomialRingZq = &b - &a;
149    /// ```
150    fn sub(self, other: &PolynomialRingZq) -> Self::Output {
151        let mut out = PolynomialRingZq::from((&PolyOverZ::default(), &other.modulus));
152        unsafe {
153            fq_sub(
154                &mut out.poly.poly,
155                &self.poly,
156                &other.poly.poly,
157                other.modulus.get_fq_ctx(),
158            );
159        }
160        out
161    }
162}
163
164arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZ, PolynomialRingZq, PolynomialRingZq);
165arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZ, PolynomialRingZq, PolynomialRingZq);
166
167impl Sub<&PolyOverQ> for &PolyOverZ {
168    type Output = PolyOverQ;
169    /// Implements the [`Sub`] trait for [`PolyOverZ`] and [`PolyOverQ`].
170    /// [`Sub`] is implemented for any combination of owned and borrowed values.
171    ///
172    /// Parameters:
173    /// - `other`: specifies the polynomial to subtract from `self`
174    ///
175    /// Returns the subtraction of both polynomials as a [`PolyOverQ`].
176    ///
177    /// # Examples
178    /// ```
179    /// use qfall_math::rational::PolyOverQ;
180    /// use qfall_math::integer::PolyOverZ;
181    /// use std::str::FromStr;
182    ///
183    /// let a = PolyOverZ::from_str("4  2 0 3 1").unwrap();
184    /// let b = PolyOverQ::from_str("4  1/2 0 3/7 1").unwrap();
185    ///
186    /// let c: PolyOverQ = &a - &b;
187    /// ```
188    fn sub(self, other: &PolyOverQ) -> Self::Output {
189        let mut out = PolyOverQ::default();
190        unsafe {
191            fmpq_poly_sub(&mut out.poly, &PolyOverQ::from(self).poly, &other.poly);
192        }
193        out
194    }
195}
196
197arithmetic_trait_borrowed_to_owned!(Sub, sub, PolyOverZ, PolyOverQ, PolyOverQ);
198arithmetic_trait_mixed_borrowed_owned!(Sub, sub, PolyOverZ, PolyOverQ, PolyOverQ);
199
200#[cfg(test)]
201mod test_sub_assign {
202    use super::PolyOverZ;
203    use std::str::FromStr;
204
205    /// Ensure that `sub_assign` works for small numbers.
206    #[test]
207    fn correct_small() {
208        let mut a = PolyOverZ::from_str("3  -1 2 -3").unwrap();
209        let b = PolyOverZ::from_str("5  -1 -2 -5 -1 -2").unwrap();
210        let cmp = PolyOverZ::from_str("5  0 4 2 1 2").unwrap();
211
212        a -= b;
213
214        assert_eq!(cmp, a);
215    }
216
217    /// Ensure that `sub_assign` works for large numbers.
218    #[test]
219    fn correct_large() {
220        let mut a =
221            PolyOverZ::from_str(&format!("3  {} {} {}", u32::MAX, i32::MIN, i32::MAX)).unwrap();
222        let b = PolyOverZ::from_str(&format!("2  -{} -{}", u32::MAX, i32::MAX)).unwrap();
223        let cmp = PolyOverZ::from_str(&format!("3  {} -1 {}", u64::from(u32::MAX) * 2, i32::MAX))
224            .unwrap();
225
226        a -= b;
227
228        assert_eq!(cmp, a);
229    }
230
231    /// Ensure that `sub_assign` is available for all types.
232    #[test]
233    fn availability() {
234        let mut a = PolyOverZ::from_str("3  1 2 -3").unwrap();
235        let b = PolyOverZ::from_str("3  -1 -2 3").unwrap();
236
237        a -= &b;
238        a -= b;
239    }
240}
241
242#[cfg(test)]
243mod test_sub {
244    use super::PolyOverZ;
245    use std::str::FromStr;
246
247    /// Testing subtraction for two [`PolyOverZ`]
248    #[test]
249    fn sub() {
250        let a: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
251        let b: PolyOverZ = PolyOverZ::from_str("5  1 2 5 1 2").unwrap();
252        let c: PolyOverZ = a - b;
253        assert_eq!(c, PolyOverZ::from_str("5  0 0 -8 -1 -2").unwrap());
254    }
255
256    /// Testing subtraction for two borrowed [`PolyOverZ`]
257    #[test]
258    fn sub_borrow() {
259        let a: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
260        let b: PolyOverZ = PolyOverZ::from_str("5  1 2 5 1 2").unwrap();
261        let c: PolyOverZ = &a - &b;
262        assert_eq!(c, PolyOverZ::from_str("5  0 0 -8 -1 -2").unwrap());
263    }
264
265    /// Testing subtraction for borrowed [`PolyOverZ`] and [`PolyOverZ`]
266    #[test]
267    fn sub_first_borrowed() {
268        let a: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
269        let b: PolyOverZ = PolyOverZ::from_str("5  1 2 5 1 2").unwrap();
270        let c: PolyOverZ = &a - b;
271        assert_eq!(c, PolyOverZ::from_str("5  0 0 -8 -1 -2").unwrap());
272    }
273
274    /// Testing subtraction for [`PolyOverZ`] and borrowed [`PolyOverZ`]
275    #[test]
276    fn sub_second_borrowed() {
277        let a: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
278        let b: PolyOverZ = PolyOverZ::from_str("5  1 2 5 1 2").unwrap();
279        let c: PolyOverZ = a - &b;
280        assert_eq!(c, PolyOverZ::from_str("5  0 0 -8 -1 -2").unwrap());
281    }
282
283    /// Testing subtraction with eliminating coefficients
284    #[test]
285    fn sub_eliminating_coefficients() {
286        let a: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
287        let b: PolyOverZ = PolyOverZ::from_str("3  1 2 -3").unwrap();
288        let c: PolyOverZ = a - b;
289        assert_eq!(c, PolyOverZ::default());
290    }
291
292    /// Testing subtraction for large [`PolyOverZ`]
293    #[test]
294    fn sub_large_numbers() {
295        let a: PolyOverZ =
296            PolyOverZ::from_str(&format!("3  {} {} {}", u32::MAX, i32::MIN, i32::MAX)).unwrap();
297        let b: PolyOverZ = PolyOverZ::from_str(&format!("2  {} {}", u32::MAX, i32::MAX)).unwrap();
298        let c: PolyOverZ = a - b;
299        assert_eq!(
300            c,
301            PolyOverZ::from_str(&format!(
302                "3  0 {} {}",
303                i64::from(i32::MIN) * 2 + 1,
304                i32::MAX
305            ))
306            .unwrap()
307        );
308    }
309}
310
311#[cfg(test)]
312mod test_mul_poly_over_zq {
313    use super::PolyOverZq;
314    use crate::integer::PolyOverZ;
315    use std::str::FromStr;
316
317    /// Checks if polynomial subtraction works fine for both borrowed
318    #[test]
319    fn borrowed_correctness() {
320        let poly_1 = PolyOverZ::from_str("2  1 2").unwrap();
321        let poly_2 = PolyOverZq::from_str(&format!("1  {} mod {}", i64::MAX, u64::MAX)).unwrap();
322
323        let poly_cmp =
324            PolyOverZq::from_str(&format!("2  {} 2 mod {}", -i64::MAX as i128 + 1, u64::MAX))
325                .unwrap();
326
327        let poly_1 = &poly_1 - &poly_2;
328
329        assert_eq!(poly_cmp, poly_1);
330    }
331
332    /// Checks if subtraction works fine for different types
333    #[test]
334    fn availability() {
335        let poly = PolyOverZq::from_str("3  1 2 3 mod 17").unwrap();
336        let z = PolyOverZ::from(2);
337
338        _ = z.clone() - poly.clone();
339        _ = &z - &poly;
340        _ = z.clone() - &poly;
341        _ = &z - poly.clone();
342    }
343}
344
345#[cfg(test)]
346mod test_sub_poly_ring_zq {
347    use super::PolynomialRingZq;
348    use crate::integer::PolyOverZ;
349    use std::str::FromStr;
350
351    /// Checks if polynomial subtraction works fine for both borrowed
352    #[test]
353    fn borrowed_correctness() {
354        let poly_1 =
355            PolynomialRingZq::from_str(&format!("2  2 {} / 4  1 2 3 4 mod {}", i64::MAX, u64::MAX))
356                .unwrap();
357        let poly_2 = PolynomialRingZq::from_str(&format!(
358            "2  -1 -{} / 4  1 2 3 4 mod {}",
359            i64::MAX as u64 - 2,
360            u64::MAX
361        ))
362        .unwrap();
363        let poly = PolyOverZ::from_str("2  1 2").unwrap();
364
365        let poly_1 = &poly - &poly_1;
366
367        assert_eq!(poly_2, poly_1);
368    }
369
370    /// Checks if subtraction works fine for different types
371    #[test]
372    fn availability() {
373        let poly = PolynomialRingZq::from_str("3  1 2 3 / 4  1 2 3 4 mod 17").unwrap();
374        let z = PolyOverZ::from(2);
375
376        _ = z.clone() - poly.clone();
377        _ = &z - &poly;
378        _ = z.clone() - &poly;
379        _ = &z - poly.clone();
380    }
381}
382
383#[cfg(test)]
384mod test_mul_poly_over_q {
385    use super::PolyOverQ;
386    use crate::integer::PolyOverZ;
387    use std::str::FromStr;
388
389    /// Checks if polynomial subtraction works fine for both borrowed
390    #[test]
391    fn borrowed_correctness() {
392        let poly_1 = PolyOverZ::from_str("2  1 2").unwrap();
393        let poly_2 = PolyOverQ::from_str(&format!("1  1/{}", i64::MAX)).unwrap();
394        let poly_cmp =
395            PolyOverQ::from_str(&format!("2  {}/{} 2", i64::MAX as i128 - 1, i64::MAX)).unwrap();
396
397        let poly_1 = &poly_1 - &poly_2;
398
399        assert_eq!(poly_cmp, poly_1);
400    }
401
402    /// Checks if subtraction works fine for different types
403    #[test]
404    fn availability() {
405        let poly = PolyOverQ::from_str("3  1/2 2 3/7").unwrap();
406        let z = PolyOverZ::from(2);
407
408        _ = z.clone() - poly.clone();
409        _ = &z - &poly;
410        _ = z.clone() - &poly;
411        _ = &z - poly.clone();
412    }
413}
qfall_math/integer/poly_over_z/arithmetic/sub.rs

qfall_math/integer/poly_over_z/arithmetic/
sub.rs
