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

qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
sub.rs
