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

qfall_math/integer/poly_over_z/arithmetic/
modulo.rs
