qfall_math/integer/poly_over_z/
reduce.rs

1// Copyright © 2023 Marvin Beckmann
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//! This module allows to simulate functionality of the polynomial ring `Z[X]/f(x)`
10//! by reducing a [`PolyOverZ`] by a [`PolyOverZ`] that
11//! has a leading coefficient of `1`.
12
13use super::{PolyOverZ, fmpz_poly_helpers::reduce_fmpz_poly_by_poly_over_z};
14
15impl PolyOverZ {
16    /// Reduces a polynomial by a polynomial `modulus`.
17    /// The modulus must have a leading coefficient of `1`, else the function will panic.
18    ///
19    /// Parameters:
20    /// - `modulus`: Specifies the polynomial by which `self` is reduced
21    ///
22    /// # Examples
23    /// ```
24    /// use qfall_math::integer::PolyOverZ;
25    /// use std::str::FromStr;
26    ///
27    /// let mut a = PolyOverZ::from_str("4  0 0 2 3").unwrap();
28    /// let modulus = PolyOverZ::from_str("3  0 1 1").unwrap();
29    ///
30    /// a.reduce_by_poly(&modulus);
31    ///
32    /// assert_eq!(PolyOverZ::from_str("2  0 1").unwrap(), a);
33    /// ```
34    ///
35    /// # Panics ...
36    /// - if the modulus does not have a leading coefficient of `1`.
37    pub fn reduce_by_poly(&mut self, modulus: &PolyOverZ) {
38        unsafe { reduce_fmpz_poly_by_poly_over_z(&mut self.poly, modulus) }
39    }
40}
41
42#[cfg(test)]
43mod test_reduce_by_poly {
44    use crate::integer::PolyOverZ;
45    use std::str::FromStr;
46
47    /// Ensures that the reduction works properly for a fixed polynomial that has to be
48    /// reduce or more than one coefficient.
49    #[test]
50    fn reduce_more_than_once() {
51        let mut a = PolyOverZ::from_str("4  0 1 2 3").unwrap();
52        let modulus = PolyOverZ::from_str("3  0 1 1").unwrap();
53
54        a.reduce_by_poly(&modulus);
55
56        assert_eq!(PolyOverZ::from_str("2  0 2").unwrap(), a);
57    }
58
59    /// Ensures that the function panics, if the leading coefficient is not `1`.
60    #[test]
61    #[should_panic]
62    fn no_leading_zero() {
63        let mut a = PolyOverZ::from_str("3  1 2 3").unwrap();
64        let modulus = PolyOverZ::from_str("2  1 2").unwrap();
65
66        a.reduce_by_poly(&modulus);
67    }
68
69    /// Ensures that large coefficients are reduced properly.
70    #[test]
71    fn large_coefficients() {
72        let mut a = PolyOverZ::from_str(&format!("3  1 -{} -1", u64::MAX)).unwrap();
73        let modulus = PolyOverZ::from_str(&format!("2  {} 1", u64::MAX)).unwrap();
74
75        a.reduce_by_poly(&modulus);
76
77        assert_eq!(PolyOverZ::from(1), a);
78    }
79}
qfall_math/integer/poly_over_z/reduce.rs

qfall_math/integer/poly_over_z/
reduce.rs
