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

qfall_math/integer/poly_over_z/arithmetic/
sub.rs
