qfall_math/integer/mat_poly_over_z/arithmetic/
modulo.rs

1// Copyright © 2025 Marcel Luca Schmidt, 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//! Implementation of the [`Rem`] trait for [`MatPolyOverZ`] values.
10
11use super::super::MatPolyOverZ;
12use crate::{
13    integer::Z,
14    integer_mod_q::{MatPolynomialRingZq, Modulus, ModulusPolynomialRingZq},
15    macros::{
16        arithmetics::{arithmetic_trait_borrowed_to_owned, arithmetic_trait_mixed_borrowed_owned},
17        for_others::implement_for_others,
18    },
19    traits::{MatrixDimensions, MatrixGetEntry, MatrixSetEntry},
20};
21use std::ops::Rem;
22
23impl Rem<&Z> for &MatPolyOverZ {
24    type Output = MatPolyOverZ;
25    /// Computes `self` mod `modulus` as long as `modulus` is greater than 1.
26    /// For negative entries in `self`, the smallest positive representative is returned.
27    ///
28    /// Parameters:
29    /// - `modulus`: specifies a non-zero integer
30    ///   over which the positive remainders are computed
31    ///
32    /// Returns `self` mod `modulus` as a [`MatPolyOverZ`] instance.
33    ///
34    /// # Examples
35    /// ```
36    /// use qfall_math::integer::{MatPolyOverZ, Z};
37    /// use std::str::FromStr;
38    ///
39    /// let a: MatPolyOverZ = MatPolyOverZ::from_str("[[2  1 -2],[1  42]]").unwrap();
40    /// let b: Z = Z::from(24);
41    ///
42    /// let c: MatPolyOverZ = a % b;
43    /// ```
44    ///
45    /// # Panics ...
46    /// - if `modulus` is smaller than `2`.
47    fn rem(self, modulus: &Z) -> Self::Output {
48        assert!(modulus > &1, "Modulus can not be smaller than 2.");
49        let num_cols = self.get_num_columns();
50        let num_rows = self.get_num_rows();
51
52        let mut out = MatPolyOverZ::new(num_rows, num_cols);
53
54        for i in 0..num_rows {
55            for j in 0..num_cols {
56                let mut entry = unsafe { self.get_entry_unchecked(i, j) };
57                entry = entry % modulus;
58                unsafe { out.set_entry_unchecked(i, j, entry) };
59            }
60        }
61
62        out
63    }
64}
65
66impl Rem<&Modulus> for &MatPolyOverZ {
67    type Output = MatPolyOverZ;
68    /// Computes `self` mod `modulus` as long as `modulus` is greater than 1.
69    /// For negative entries in `self`, the smallest positive representative is returned.
70    ///
71    /// Parameters:
72    /// - `modulus`: specifies a non-zero integer
73    ///   over which the positive remainders are computed
74    ///
75    /// Returns `self` mod `modulus` as a [`MatPolyOverZ`] instance.
76    ///
77    /// # Examples
78    /// ```
79    /// use qfall_math::integer::MatPolyOverZ;
80    /// use qfall_math::integer_mod_q::Modulus;
81    /// use std::str::FromStr;
82    ///
83    /// let a: MatPolyOverZ = MatPolyOverZ::from_str("[[2  1 -2],[1  42]]").unwrap();
84    /// let b = Modulus::from(24);
85    ///
86    /// let c: MatPolyOverZ = &a % &b;
87    /// ```
88    fn rem(self, modulus: &Modulus) -> Self::Output {
89        let mut out = MatPolyOverZ::new(self.get_num_rows(), self.get_num_rows());
90
91        for i in 0..self.get_num_rows() {
92            for j in 0..self.get_num_columns() {
93                let mut entry = unsafe { self.get_entry_unchecked(i, j) };
94                entry = entry % modulus;
95                unsafe { out.set_entry_unchecked(i, j, entry) };
96            }
97        }
98
99        out
100    }
101}
102
103impl<Mod: Into<ModulusPolynomialRingZq>> Rem<Mod> for &MatPolyOverZ {
104    type Output = MatPolyOverZ;
105    /// Computes `self` mod `modulus` as long as `modulus` is greater than 1.
106    /// For negative entries in `self`, the smallest positive representative is returned.
107    ///
108    /// Parameters:
109    /// - `modulus`: specifies a non-zero integer
110    ///   over which the positive remainders are computed
111    ///
112    /// Returns `self` mod `modulus` as a [`MatPolyOverZ`] instance.
113    ///
114    /// # Examples
115    /// ```
116    /// use qfall_math::integer::MatPolyOverZ;
117    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
118    /// use std::str::FromStr;
119    ///
120    /// let a: MatPolyOverZ = MatPolyOverZ::from_str("[[2  1 -2],[1  42]]").unwrap();
121    /// let b = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
122    ///
123    /// let c: MatPolyOverZ = &a % &b;
124    /// ```
125    fn rem(self, modulus: Mod) -> Self::Output {
126        MatPolynomialRingZq::from((self, modulus)).matrix
127    }
128}
129
130impl<Mod: Into<ModulusPolynomialRingZq>> Rem<Mod> for MatPolyOverZ {
131    type Output = MatPolyOverZ;
132    /// Computes `self` mod `modulus` as long as `modulus` is greater than 1.
133    /// For negative entries in `self`, the smallest positive representative is returned.
134    ///
135    /// Parameters:
136    /// - `modulus`: specifies a non-zero integer
137    ///   over which the positive remainders are computed
138    ///
139    /// Returns `self` mod `modulus` as a [`MatPolyOverZ`] instance.
140    ///
141    /// # Examples
142    /// ```
143    /// use qfall_math::integer::MatPolyOverZ;
144    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
145    /// use std::str::FromStr;
146    ///
147    /// let a: MatPolyOverZ = MatPolyOverZ::from_str("[[2  1 -2],[1  42]]").unwrap();
148    /// let b = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
149    ///
150    /// let c: MatPolyOverZ = &a % &b;
151    /// ```
152    fn rem(self, modulus: Mod) -> Self::Output {
153        MatPolynomialRingZq::from((self, modulus)).matrix
154    }
155}
156
157arithmetic_trait_borrowed_to_owned!(Rem, rem, MatPolyOverZ, Z, MatPolyOverZ);
158arithmetic_trait_mixed_borrowed_owned!(Rem, rem, MatPolyOverZ, Z, MatPolyOverZ);
159arithmetic_trait_borrowed_to_owned!(Rem, rem, MatPolyOverZ, Modulus, MatPolyOverZ);
160arithmetic_trait_mixed_borrowed_owned!(Rem, rem, MatPolyOverZ, Modulus, MatPolyOverZ);
161
162implement_for_others!(Z, MatPolyOverZ, Rem for i8 i16 i32 i64 u8 u16 u32 u64);
163
164#[cfg(test)]
165mod test_rem {
166    use super::Z;
167    use crate::{
168        integer::MatPolyOverZ,
169        integer_mod_q::{Modulus, ModulusPolynomialRingZq, PolyOverZq},
170    };
171    use std::str::FromStr;
172
173    /// Testing modulo for two owned
174    #[test]
175    fn rem() {
176        let a = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap();
177        let b = Z::from(24);
178        let modulus = Modulus::from(24);
179        let poly_mod = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
180        let c1 = a.clone() % b;
181        let c2 = a.clone() % modulus;
182        let c3 = a % poly_mod;
183        let cmp = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 18, 0]]").unwrap();
184        assert_eq!(c1, cmp);
185        assert_eq!(c2, cmp);
186        assert_eq!(c3, cmp);
187    }
188
189    /// Testing modulo for two borrowed
190    #[test]
191    fn rem_borrow() {
192        let a = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap();
193        let b = Z::from(24);
194        let modulus = Modulus::from(24);
195        let poly_mod = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
196        let c1 = &a % &b;
197        let c2 = &a % &modulus;
198        let c3 = &a % &poly_mod;
199        let cmp = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 18, 0]]").unwrap();
200        assert_eq!(c1, cmp);
201        assert_eq!(c2, cmp);
202        assert_eq!(c3, cmp);
203    }
204
205    /// Testing modulo for borrowed and owned
206    #[test]
207    fn rem_first_borrowed() {
208        let a = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap();
209        let b = Z::from(24);
210        let modulus = Modulus::from(24);
211        let poly_mod = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
212        let c1 = &a % b;
213        let c2 = &a % modulus;
214        let c3 = &a % poly_mod;
215        let cmp = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 18, 0]]").unwrap();
216        assert_eq!(c1, cmp);
217        assert_eq!(c2, cmp);
218        assert_eq!(c3, cmp);
219    }
220
221    /// Testing modulo for owned and borrowed
222    #[test]
223    fn rem_second_borrowed() {
224        let a = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap();
225        let b = Z::from(24);
226        let modulus = Modulus::from(24);
227        let poly_mod = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
228        let c1 = a.clone() % &b;
229        let c2 = a.clone() % &modulus;
230        let c3 = a % &poly_mod;
231        let cmp = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 18, 0]]").unwrap();
232        assert_eq!(c1, cmp);
233        assert_eq!(c2, cmp);
234        assert_eq!(c3, cmp);
235    }
236
237    /// Testing modulo for negative values
238    #[test]
239    fn rem_negative_representation() {
240        let a = MatPolyOverZ::from_str("[[1  -2, 1  3],[2  3 42, 1  24]]").unwrap();
241        let b = Z::from(24);
242        let modulus = Modulus::from(24);
243        let poly_mod = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
244        let c1 = &a % &b;
245        let c2 = &a % &modulus;
246        let c3 = a % &poly_mod;
247        let cmp = MatPolyOverZ::from_str("[[1  22, 1  3],[2  3 18, 0]]").unwrap();
248        assert_eq!(c1, cmp);
249        assert_eq!(c2, cmp);
250        assert_eq!(c3, cmp);
251    }
252
253    /// Testing modulo for large numbers
254    #[test]
255    fn rem_large_numbers() {
256        let a =
257            MatPolyOverZ::from_str(&format!("[[1  2, 1  {}],[2  3 42, 1  24]]", u64::MAX)).unwrap();
258        let b = Z::from(u64::MAX - 2);
259        let modulus = Modulus::from(u64::MAX - 2);
260        let poly_mod =
261            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {}", u64::MAX - 2)).unwrap();
262        let c1 = a.clone() % &b;
263        let c2 = a.clone() % &modulus;
264        let c3 = a % &poly_mod;
265        let cmp = MatPolyOverZ::from_str("[[1  2, 1  2],[2  3 42, 1  24]]").unwrap();
266        assert_eq!(c1, cmp);
267        assert_eq!(c2, cmp);
268        assert_eq!(c3, cmp);
269    }
270
271    /// Ensure that the reduction with a polynomial modulus also reduces the polynomial degree.
272    #[test]
273    fn polynomial_reduction() {
274        let a = MatPolyOverZ::from_str("[[1  -2, 4  1 1 0 1],[2  3 42, 1  24]]").unwrap();
275        let b = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
276        let c = a % b;
277        let cmp = MatPolyOverZ::from_str("[[1  22, 2  0 1],[2  3 18, 0]]").unwrap();
278        assert_eq!(c, cmp);
279    }
280
281    /// Ensures that computing modulo a negative number results in a panic
282    #[test]
283    #[should_panic]
284    fn rem_negative_error() {
285        let a = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap();
286        let b = Z::from(-24);
287        _ = &a % &b;
288    }
289
290    /// Ensures that computing modulo 0 results in a panic
291    #[test]
292    #[should_panic]
293    fn zero_modulus() {
294        _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 0;
295    }
296
297    /// Ensures that `modulo` is available for several types implementing [`Into<Z>`].
298    #[test]
299    fn availability() {
300        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2u8;
301        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2u16;
302        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2u32;
303        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2u64;
304        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2i8;
305        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2i16;
306        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2i32;
307        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2i64;
308        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % Z::from(2);
309        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap()
310            % ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 24").unwrap();
311
312        let _ = &MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % 2u8;
313        let _ = MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % &Z::from(2);
314        let _ = &MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap() % &Z::from(2);
315        let _ = &MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap()
316            % PolyOverZq::from_str("4  1 0 0 1 mod 24").unwrap();
317        let _ = &MatPolyOverZ::from_str("[[1  2, 1  3],[2  3 42, 1  24]]").unwrap()
318            % &PolyOverZq::from_str("4  1 0 0 1 mod 24").unwrap();
319    }
320}
qfall_math/integer/mat_poly_over_z/arithmetic/modulo.rs

qfall_math/integer/mat_poly_over_z/arithmetic/
modulo.rs
