qfall_math/integer/mat_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 matrices over the polynomial ring
10//! `Z[X]/f(x)` by entrywise reducing a [`MatPolyOverZ`] by a [`PolyOverZ`] that
11//! has a leading coefficient of `1`.
12
13use super::MatPolyOverZ;
14use crate::{
15    integer::{PolyOverZ, poly_over_z::fmpz_poly_helpers::reduce_fmpz_poly_by_poly_over_z},
16    traits::MatrixDimensions,
17};
18use flint_sys::fmpz_poly_mat::fmpz_poly_mat_entry;
19
20impl MatPolyOverZ {
21    /// Entrywise reduces a matrix of polynomials by a polynomial `modulus`.
22    /// The modulus must have a leading coefficient of `1`, else the function will panic.
23    ///
24    /// Parameters:
25    /// - `modulus`: Specifies the polynomial by which `self` is reduced
26    ///
27    /// # Examples
28    /// ```
29    /// use qfall_math::integer::{MatPolyOverZ, PolyOverZ};
30    /// use std::str::FromStr;
31    ///
32    /// let mut a = MatPolyOverZ::from_str("[[4  0 1 2 3, 3  0 1 1]]").unwrap();
33    /// let modulus = PolyOverZ::from_str("3  0 1 1").unwrap();
34    ///
35    /// a.reduce_by_poly(&modulus);
36    ///
37    /// assert_eq!(MatPolyOverZ::from_str("[[2  0 2, 0]]").unwrap(), a);
38    /// ```
39    ///
40    /// # Panics ...
41    /// - if the modulus does not have a leading coefficient of `1`.
42    pub fn reduce_by_poly(&mut self, modulus: &PolyOverZ) {
43        for i in 0..self.get_num_rows() {
44            for j in 0..self.get_num_columns() {
45                unsafe {
46                    let entry = fmpz_poly_mat_entry(&self.matrix, i, j);
47                    if (*entry).length > modulus.get_degree() {
48                        reduce_fmpz_poly_by_poly_over_z(&mut *entry, modulus);
49                    }
50                }
51            }
52        }
53    }
54}
55
56#[cfg(test)]
57mod test_reduce_by_poly {
58    use crate::integer::{MatPolyOverZ, PolyOverZ};
59    use std::str::FromStr;
60
61    /// Ensures that the reduction works properly for a fixed polynomial that has to be
62    /// reduce or more than one coefficient.
63    #[test]
64    fn reduce_more_than_once() {
65        let mut a = MatPolyOverZ::from_str("[[4  0 1 2 3, 3  0 1 1]]").unwrap();
66        let modulus = PolyOverZ::from_str("3  0 1 1").unwrap();
67
68        a.reduce_by_poly(&modulus);
69
70        assert_eq!(MatPolyOverZ::from_str("[[2  0 2, 0]]").unwrap(), a);
71    }
72
73    /// Ensures that the function panics, if the leading coefficient is not `1`.
74    #[test]
75    #[should_panic]
76    fn no_leading_zero() {
77        let mut a = MatPolyOverZ::from_str("[[3  1 2 3]]").unwrap();
78        let modulus = PolyOverZ::from_str("2  1 2").unwrap();
79
80        a.reduce_by_poly(&modulus);
81    }
82
83    /// Ensures that large coefficients are reduced properly.
84    #[test]
85    fn large_coefficients() {
86        let mut a = MatPolyOverZ::from_str(&format!(
87            "[[3  1 -{} -1, 1  1],[1  -1, 4  0 0 {} 1]]",
88            u64::MAX,
89            u64::MAX
90        ))
91        .unwrap();
92        let modulus = PolyOverZ::from_str(&format!("2  {} 1", u64::MAX)).unwrap();
93
94        a.reduce_by_poly(&modulus);
95
96        let cmp_mat = MatPolyOverZ::from_str("[[1  1, 1  1],[1  -1, 0]]").unwrap();
97        assert_eq!(cmp_mat, a);
98    }
99
100    /// Ensures that the zero polynomial does not cause problems.
101    #[test]
102    fn zero_polynomial() {
103        let mut a = MatPolyOverZ::from_str("[[0, 0]]").unwrap();
104        let modulus = PolyOverZ::from_str(&format!("2  {} 1", u64::MAX)).unwrap();
105
106        a.reduce_by_poly(&modulus);
107    }
108}
qfall_math/integer/mat_poly_over_z/reduce.rs

qfall_math/integer/mat_poly_over_z/
reduce.rs
