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

qfall_math/integer/poly_over_z/arithmetic/
sub.rs
