qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
sub.rs

1// Copyright © 2025 Niklas Siemer
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 subtraction for [`NTTPolynomialRingZq`].
10
11use crate::{
12    integer::Z,
13    integer_mod_q::NTTPolynomialRingZq,
14    macros::arithmetics::{
15        arithmetic_assign_trait_borrowed_to_owned, arithmetic_trait_borrowed_to_owned,
16        arithmetic_trait_mixed_borrowed_owned,
17    },
18    traits::CompareBase,
19};
20use flint_sys::fmpz_mod::fmpz_mod_sub;
21use std::ops::{Sub, SubAssign};
22
23impl Sub for &NTTPolynomialRingZq {
24    type Output = NTTPolynomialRingZq;
25
26    /// Subtracts `other` from `self`.
27    ///
28    /// Paramters:
29    /// - `other`: specifies the NTT-representation of the polynomial to subtract from `self`
30    ///
31    /// Returns the NTT-representation of the subtraction of `other` from `self`.
32    ///
33    /// # Example
34    /// ```
35    /// use qfall_math::integer_mod_q::{NTTPolynomialRingZq, ModulusPolynomialRingZq};
36    /// use std::str::FromStr;
37    /// let mut modulus = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
38    /// modulus.set_ntt_unchecked(64);
39    ///
40    /// let a = NTTPolynomialRingZq::sample_uniform(&modulus);
41    /// let b = NTTPolynomialRingZq::sample_uniform(&modulus);
42    ///
43    /// let c = a - b;
44    /// ```
45    ///
46    /// # Panics ...
47    /// - if the moduli are not equal.
48    fn sub(self, other: Self) -> Self::Output {
49        assert_eq!(
50            self.modulus, other.modulus,
51            "The moduli of both polynomials have to be equal for subtraction."
52        );
53        let binding = &self.modulus.get_q_as_modulus();
54        let mod_q = binding.get_fmpz_mod_ctx_struct();
55
56        let mut out = NTTPolynomialRingZq {
57            poly: vec![Z::default(); self.poly.len()],
58            modulus: self.modulus.clone(),
59        };
60
61        for i in 0..self.poly.len() {
62            unsafe {
63                fmpz_mod_sub(
64                    &mut out.poly[i].value,
65                    &self.poly[i].value,
66                    &other.poly[i].value,
67                    mod_q,
68                );
69            }
70        }
71
72        out
73    }
74}
75
76arithmetic_trait_borrowed_to_owned!(
77    Sub,
78    sub,
79    NTTPolynomialRingZq,
80    NTTPolynomialRingZq,
81    NTTPolynomialRingZq
82);
83arithmetic_trait_mixed_borrowed_owned!(
84    Sub,
85    sub,
86    NTTPolynomialRingZq,
87    NTTPolynomialRingZq,
88    NTTPolynomialRingZq
89);
90
91impl SubAssign<&NTTPolynomialRingZq> for NTTPolynomialRingZq {
92    /// Subtracts `other` from `self` reusing the memory of `self`.
93    ///
94    /// Paramters:
95    /// - `other`: specifies the NTT-representation of the polynomial to subtract from `self`
96    ///
97    /// Computes the NTT-representation of the subtraction of `other` from `self`.
98    ///
99    /// # Example
100    /// ```
101    /// use qfall_math::integer_mod_q::{NTTPolynomialRingZq, ModulusPolynomialRingZq};
102    /// use std::str::FromStr;
103    /// let mut modulus = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
104    /// modulus.set_ntt_unchecked(64);
105    ///
106    /// let mut a = NTTPolynomialRingZq::sample_uniform(&modulus);
107    /// let b = NTTPolynomialRingZq::sample_uniform(&modulus);
108    ///
109    /// a -= b;
110    /// ```
111    ///
112    /// # Panics ...
113    /// - if the moduli are not equal.
114    fn sub_assign(&mut self, other: &Self) {
115        if !self.compare_base(other) {
116            panic!("{}", self.call_compare_base_error(other).unwrap());
117        }
118        let binding = &self.modulus.get_q_as_modulus();
119        let mod_q = binding.get_fmpz_mod_ctx_struct();
120
121        for i in 0..self.poly.len() {
122            unsafe {
123                fmpz_mod_sub(
124                    &mut self.poly[i].value,
125                    &self.poly[i].value,
126                    &other.poly[i].value,
127                    mod_q,
128                );
129            }
130        }
131    }
132}
133
134arithmetic_assign_trait_borrowed_to_owned!(
135    SubAssign,
136    sub_assign,
137    NTTPolynomialRingZq,
138    NTTPolynomialRingZq
139);
140
141#[cfg(test)]
142mod test_sub {
143    use crate::{
144        integer_mod_q::{
145            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
146        },
147        traits::SetCoefficient,
148    };
149    use std::{ops::Sub, str::FromStr};
150
151    /// Ensure that the entrywise subtraction and the intuitive subtraction yields
152    /// the same results for the parameters from Dilithium.
153    #[test]
154    fn test_dilithium_params() {
155        let n = 256;
156        let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;
157
158        let mut mod_poly = PolyOverZq::from(modulus);
159        mod_poly.set_coeff(0, 1).unwrap();
160        mod_poly.set_coeff(n, 1).unwrap();
161
162        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
163
164        polynomial_modulus.set_ntt_unchecked(1753);
165
166        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
167        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
168
169        let ntt1 = NTTPolynomialRingZq::from(&p1);
170        let ntt2 = NTTPolynomialRingZq::from(&p2);
171
172        let res = ntt1.sub(ntt2);
173
174        assert_eq!(&p1 - &p2, PolynomialRingZq::from(res))
175    }
176
177    /// Ensure that the entrywise subtraction and the intuitive subtraction yields
178    /// the same results for the parameters from Hawk1024.
179    #[test]
180    fn test_hawk1024_params() {
181        let n = 1024;
182        let modulus = 12289;
183
184        let mut mod_poly = PolyOverZq::from(modulus);
185        mod_poly.set_coeff(0, 1).unwrap();
186        mod_poly.set_coeff(n, 1).unwrap();
187
188        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
189
190        polynomial_modulus.set_ntt_unchecked(1945);
191
192        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
193        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
194
195        let ntt1 = NTTPolynomialRingZq::from(&p1);
196        let ntt2 = NTTPolynomialRingZq::from(&p2);
197
198        let res = ntt1.sub(&ntt2);
199
200        assert_eq!(&p1 - &p2, PolynomialRingZq::from(res))
201    }
202
203    /// Ensures that the function panics for differing moduli.
204    #[test]
205    #[should_panic]
206    fn different_moduli() {
207        let mut modulus0 = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
208        modulus0.set_ntt_unchecked(64);
209        let mut modulus1 = ModulusPolynomialRingZq::from_str("6  1 0 0 0 0 1 mod 257").unwrap();
210        modulus1.set_ntt_unchecked(64);
211
212        let a = NTTPolynomialRingZq::sample_uniform(&modulus0);
213        let b = NTTPolynomialRingZq::sample_uniform(&modulus1);
214
215        let _ = a - b;
216    }
217}
218
219#[cfg(test)]
220mod test_sub_assign {
221    use crate::{
222        integer_mod_q::{
223            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
224        },
225        traits::SetCoefficient,
226    };
227    use std::{ops::SubAssign, str::FromStr};
228
229    /// Ensure that the entrywise subtraction and the intuitive subtraction yields
230    /// the same results for the parameters from Dilithium.
231    #[test]
232    fn test_dilithium_params() {
233        let n = 256;
234        let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;
235
236        let mut mod_poly = PolyOverZq::from(modulus);
237        mod_poly.set_coeff(0, 1).unwrap();
238        mod_poly.set_coeff(n, 1).unwrap();
239
240        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
241
242        polynomial_modulus.set_ntt_unchecked(1753);
243
244        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
245        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
246
247        let mut ntt1 = NTTPolynomialRingZq::from(&p1);
248        let ntt2 = NTTPolynomialRingZq::from(&p2);
249
250        ntt1.sub_assign(&ntt2);
251
252        assert_eq!(&p1 - &p2, PolynomialRingZq::from(ntt1))
253    }
254
255    /// Ensure that the entrywise subtraction and the intuitive subtraction yields
256    /// the same results for the parameters from Hawk1024.
257    #[test]
258    fn test_hawk1024_params() {
259        let n = 1024;
260        let modulus = 12289;
261
262        let mut mod_poly = PolyOverZq::from(modulus);
263        mod_poly.set_coeff(0, 1).unwrap();
264        mod_poly.set_coeff(n, 1).unwrap();
265
266        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
267
268        polynomial_modulus.set_ntt_unchecked(1945);
269
270        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
271        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
272
273        let mut ntt1 = NTTPolynomialRingZq::from(&p1);
274        let ntt2 = NTTPolynomialRingZq::from(&p2);
275
276        ntt1.sub_assign(ntt2);
277
278        assert_eq!(&p1 - &p2, PolynomialRingZq::from(ntt1))
279    }
280
281    /// Ensures that the function panics for differing moduli.
282    #[test]
283    #[should_panic]
284    fn different_moduli() {
285        let mut modulus0 = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
286        modulus0.set_ntt_unchecked(64);
287        let mut modulus1 = ModulusPolynomialRingZq::from_str("6  1 0 0 0 0 1 mod 257").unwrap();
288        modulus1.set_ntt_unchecked(64);
289
290        let mut a = NTTPolynomialRingZq::sample_uniform(&modulus0);
291        let b = NTTPolynomialRingZq::sample_uniform(&modulus1);
292
293        a -= b;
294    }
295}
qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/sub.rs

qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
sub.rs
