qfall_math/integer/mat_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 [`MatZ`] values.
10
11use super::super::MatZ;
12use crate::{
13    integer::Z,
14    integer_mod_q::Modulus,
15    macros::{
16        arithmetics::{arithmetic_trait_borrowed_to_owned, arithmetic_trait_mixed_borrowed_owned},
17        for_others::implement_for_others,
18    },
19    traits::MatrixDimensions,
20};
21use flint_sys::{fmpz::fmpz_mod, fmpz_mat::fmpz_mat_entry, fmpz_mod::fmpz_mod_set_fmpz};
22use std::ops::Rem;
23
24impl Rem<&Z> for &MatZ {
25    type Output = MatZ;
26    /// Computes `self` mod `modulus` as long as `modulus` is greater than 1.
27    /// For negative entries in `self`, the smallest positive representative is returned.
28    ///
29    /// Parameters:
30    /// - `modulus`: specifies a non-zero integer
31    ///   over which the positive remainders are computed
32    ///
33    /// Returns `self` mod `modulus` as a [`MatZ`] instance.
34    ///
35    /// # Examples
36    /// ```
37    /// use qfall_math::integer::{MatZ, Z};
38    /// use std::str::FromStr;
39    ///
40    /// let a: MatZ = MatZ::from_str("[[-2],[42]]").unwrap();
41    /// let b: Z = Z::from(24);
42    ///
43    /// let c: MatZ = a % b;
44    /// ```
45    ///
46    /// # Panics ...
47    /// - if `modulus` is smaller than `2`.
48    fn rem(self, modulus: &Z) -> Self::Output {
49        assert!(modulus > &1, "Modulus can not be smaller than 2.");
50
51        let out = self.clone();
52
53        for i in 0..out.get_num_rows() {
54            for j in 0..out.get_num_columns() {
55                let entry = unsafe { fmpz_mat_entry(&out.matrix, i, j) };
56                unsafe { fmpz_mod(entry, entry, &modulus.value) }
57            }
58        }
59
60        out
61    }
62}
63
64impl Rem<&Modulus> for &MatZ {
65    type Output = MatZ;
66    /// Computes `self` mod `modulus`.
67    /// For negative entries in `self`, the smallest positive representative is returned.
68    ///
69    /// Parameters:
70    /// - `modulus`: specifies a non-zero integer
71    ///   over which the positive remainders are computed
72    ///
73    /// Returns `self` mod `modulus` as a [`MatZ`] instance.
74    ///
75    /// # Examples
76    /// ```
77    /// use qfall_math::integer::MatZ;
78    /// use qfall_math::integer_mod_q::Modulus;
79    /// use std::str::FromStr;
80    ///
81    /// let a: MatZ = MatZ::from_str("[[-2],[42]]").unwrap();
82    /// let b = Modulus::from(24);
83    ///
84    /// let c: MatZ = &a % &b;
85    /// ```
86    fn rem(self, modulus: &Modulus) -> Self::Output {
87        let out = self.clone();
88
89        for i in 0..out.get_num_rows() {
90            for j in 0..out.get_num_columns() {
91                let entry = unsafe { fmpz_mat_entry(&out.matrix, i, j) };
92                unsafe { fmpz_mod_set_fmpz(entry, entry, modulus.get_fmpz_mod_ctx_struct()) }
93            }
94        }
95
96        out
97    }
98}
99
100arithmetic_trait_borrowed_to_owned!(Rem, rem, MatZ, Z, MatZ);
101arithmetic_trait_mixed_borrowed_owned!(Rem, rem, MatZ, Z, MatZ);
102arithmetic_trait_borrowed_to_owned!(Rem, rem, MatZ, Modulus, MatZ);
103arithmetic_trait_mixed_borrowed_owned!(Rem, rem, MatZ, Modulus, MatZ);
104
105implement_for_others!(Z, MatZ, Rem for i8 i16 i32 i64 u8 u16 u32 u64);
106
107#[cfg(test)]
108mod test_rem {
109    use super::Z;
110    use crate::{integer::MatZ, integer_mod_q::Modulus};
111    use std::str::FromStr;
112
113    /// Testing modulo for two owned
114    #[test]
115    fn rem() {
116        let a = MatZ::from_str("[[2, 3],[42, 24]]").unwrap();
117        let b = Z::from(24);
118        let c1 = a.clone() % b;
119        let c2 = a % Modulus::from(24);
120        assert_eq!(c1, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
121        assert_eq!(c2, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
122    }
123
124    /// Testing modulo for two borrowed
125    #[test]
126    fn rem_borrow() {
127        let a = MatZ::from_str("[[2, 3],[42, 24]]").unwrap();
128        let b = Z::from(24);
129        let c1 = &a % &b;
130        let c2 = &a % &Modulus::from(24);
131        assert_eq!(c1, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
132        assert_eq!(c2, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
133    }
134
135    /// Testing modulo for borrowed and owned
136    #[test]
137    fn rem_first_borrowed() {
138        let a = MatZ::from_str("[[2, 3],[42, 24]]").unwrap();
139        let b = Z::from(24);
140        let c1 = &a % b;
141        let c2 = &a % Modulus::from(24);
142        assert_eq!(c1, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
143        assert_eq!(c2, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
144    }
145
146    /// Testing modulo for owned and borrowed
147    #[test]
148    fn rem_second_borrowed() {
149        let a = MatZ::from_str("[[2, 3],[42, 24]]").unwrap();
150        let b = Z::from(24);
151        let c1 = a.clone() % &b;
152        let c2 = a % &Modulus::from(24);
153        assert_eq!(c1, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
154        assert_eq!(c2, MatZ::from_str("[[2, 3],[18, 0]]").unwrap());
155    }
156
157    /// Testing modulo for negative values
158    #[test]
159    fn rem_negative_representation() {
160        let a = MatZ::from_str("[[-2, 3],[42, 24]]").unwrap();
161        let b = Z::from(24);
162        let c1 = &a % &b;
163        let c2 = &a % &Modulus::from(24);
164        assert_eq!(c1, MatZ::from_str("[[22, 3],[18, 0]]").unwrap());
165        assert_eq!(c2, MatZ::from_str("[[22, 3],[18, 0]]").unwrap());
166    }
167
168    /// Testing modulo for large numbers
169    #[test]
170    fn rem_large_numbers() {
171        let a = MatZ::from_str(&format!("[[2, 3],[{}, 24]]", u64::MAX)).unwrap();
172        let b = Z::from(u64::MAX - 2);
173        let c1 = &a % &b;
174        let c2 = &a % &Modulus::from(u64::MAX - 2);
175        assert_eq!(c1, MatZ::from_str("[[2, 3],[2, 24]]").unwrap());
176        assert_eq!(c2, MatZ::from_str("[[2, 3],[2, 24]]").unwrap());
177    }
178
179    /// Ensures that computing modulo a negative number results in a panic
180    #[test]
181    #[should_panic]
182    fn rem_negative_error() {
183        let a = MatZ::from_str("[[2, 3],[42, 24]]").unwrap();
184        let b = Z::from(-24);
185        _ = &a % &b;
186    }
187
188    /// Ensures that computing modulo 0 results in a panic
189    #[test]
190    #[should_panic]
191    fn zero_modulus() {
192        _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 0;
193    }
194
195    /// Ensures that `modulo` is available for several types.
196    #[test]
197    fn availability() {
198        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2u8;
199        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2u16;
200        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2u32;
201        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2u64;
202        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2i8;
203        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2i16;
204        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2i32;
205        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2i64;
206        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % Z::from(2);
207        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % Modulus::from(2);
208
209        let _ = &MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % 2u8;
210        let _ = MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % &Z::from(2);
211        let _ = &MatZ::from_str("[[2, 3],[42, 24]]").unwrap() % &Z::from(2);
212    }
213}
qfall_math/integer/mat_z/arithmetic/modulo.rs

qfall_math/integer/mat_z/arithmetic/
modulo.rs
