qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
add.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 addition 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_add;
21use std::ops::{Add, AddAssign};
22
23impl Add for &NTTPolynomialRingZq {
24    type Output = NTTPolynomialRingZq;
25
26    /// Adds `self` with `other`.
27    ///
28    /// Paramters:
29    /// - `other`: specifies the NTT-representation of the polynomial to add to `self`
30    ///
31    /// Returns the NTT-representation of the sum of `self` and `other`.
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 add(self, other: Self) -> Self::Output {
49        if !self.compare_base(other) {
50            panic!("{}", self.call_compare_base_error(other).unwrap());
51        }
52        let binding = &self.modulus.get_q_as_modulus();
53        let mod_q = binding.get_fmpz_mod_ctx_struct();
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_add(
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    Add,
77    add,
78    NTTPolynomialRingZq,
79    NTTPolynomialRingZq,
80    NTTPolynomialRingZq
81);
82arithmetic_trait_mixed_borrowed_owned!(
83    Add,
84    add,
85    NTTPolynomialRingZq,
86    NTTPolynomialRingZq,
87    NTTPolynomialRingZq
88);
89
90impl AddAssign<&NTTPolynomialRingZq> for NTTPolynomialRingZq {
91    /// Adds `self` with `other` reusing the memory of `self`.
92    ///
93    /// Paramters:
94    /// - `other`: specifies the NTT-representation of the polynomial to add to `self`
95    ///
96    /// Computes the NTT-representation of the sum of `self` and `other`.
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 add_assign(&mut self, other: &Self) {
114        if !self.compare_base(other) {
115            panic!("{}", self.call_compare_base_error(other).unwrap());
116        }
117        let binding = &self.modulus.get_q_as_modulus();
118        let mod_q = binding.get_fmpz_mod_ctx_struct();
119
120        for i in 0..self.poly.len() {
121            unsafe {
122                fmpz_mod_add(
123                    &mut self.poly[i].value,
124                    &self.poly[i].value,
125                    &other.poly[i].value,
126                    mod_q,
127                );
128            }
129        }
130    }
131}
132
133arithmetic_assign_trait_borrowed_to_owned!(
134    AddAssign,
135    add_assign,
136    NTTPolynomialRingZq,
137    NTTPolynomialRingZq
138);
139
140#[cfg(test)]
141mod test_add {
142    use crate::{
143        integer_mod_q::{
144            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
145        },
146        traits::SetCoefficient,
147    };
148    use std::{ops::Add, str::FromStr};
149
150    /// Ensure that the entrywise addition and the intuitive addition yields
151    /// the same results for the parameters from Dilithium.
152    #[test]
153    fn test_dilithium_params() {
154        let n = 256;
155        let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;
156
157        let mut mod_poly = PolyOverZq::from(modulus);
158        mod_poly.set_coeff(0, 1).unwrap();
159        mod_poly.set_coeff(n, 1).unwrap();
160
161        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
162
163        polynomial_modulus.set_ntt_unchecked(1753);
164
165        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
166        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
167
168        let ntt1 = NTTPolynomialRingZq::from(&p1);
169        let ntt2 = NTTPolynomialRingZq::from(&p2);
170
171        let res = (&ntt1).add(ntt2);
172
173        assert_eq!(&p1 + &p2, PolynomialRingZq::from(res))
174    }
175
176    /// Ensure that the entrywise addition and the intuitive addition yields
177    /// the same results for the parameters from Hawk1024.
178    #[test]
179    fn test_hawk1024_params() {
180        let n = 1024;
181        let modulus = 12289;
182
183        let mut mod_poly = PolyOverZq::from(modulus);
184        mod_poly.set_coeff(0, 1).unwrap();
185        mod_poly.set_coeff(n, 1).unwrap();
186
187        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
188
189        polynomial_modulus.set_ntt_unchecked(1945);
190
191        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
192        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
193
194        let ntt1 = NTTPolynomialRingZq::from(&p1);
195        let ntt2 = NTTPolynomialRingZq::from(&p2);
196
197        let res = ntt1.add(ntt2);
198
199        assert_eq!(&p1 + &p2, PolynomialRingZq::from(res))
200    }
201
202    /// Ensures that the function panics for differing moduli.
203    #[test]
204    #[should_panic]
205    fn different_moduli() {
206        let mut modulus0 = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
207        modulus0.set_ntt_unchecked(64);
208        let mut modulus1 = ModulusPolynomialRingZq::from_str("6  1 0 0 0 0 1 mod 257").unwrap();
209        modulus1.set_ntt_unchecked(64);
210
211        let a = NTTPolynomialRingZq::sample_uniform(&modulus0);
212        let b = NTTPolynomialRingZq::sample_uniform(&modulus1);
213
214        let _ = a + b;
215    }
216}
217
218#[cfg(test)]
219mod test_add_assign {
220    use crate::{
221        integer_mod_q::{
222            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
223        },
224        traits::SetCoefficient,
225    };
226    use std::{ops::AddAssign, str::FromStr};
227
228    /// Ensure that the entrywise addition and the intuitive addition yields
229    /// the same results for the parameters from Dilithium.
230    #[test]
231    fn test_dilithium_params() {
232        let n = 256;
233        let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;
234
235        let mut mod_poly = PolyOverZq::from(modulus);
236        mod_poly.set_coeff(0, 1).unwrap();
237        mod_poly.set_coeff(n, 1).unwrap();
238
239        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
240
241        polynomial_modulus.set_ntt_unchecked(1753);
242
243        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
244        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
245
246        let mut ntt1 = NTTPolynomialRingZq::from(&p1);
247        let ntt2 = NTTPolynomialRingZq::from(&p2);
248
249        ntt1.add_assign(ntt2);
250
251        assert_eq!(&p1 + &p2, PolynomialRingZq::from(ntt1))
252    }
253
254    /// Ensure that the entrywise addition and the intuitive addition yields
255    /// the same results for the parameters from Hawk1024.
256    #[test]
257    fn test_hawk1024_params() {
258        let n = 1024;
259        let modulus = 12289;
260
261        let mut mod_poly = PolyOverZq::from(modulus);
262        mod_poly.set_coeff(0, 1).unwrap();
263        mod_poly.set_coeff(n, 1).unwrap();
264
265        let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
266
267        polynomial_modulus.set_ntt_unchecked(1945);
268
269        let p1 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
270        let p2 = PolynomialRingZq::sample_uniform(&polynomial_modulus);
271
272        let mut ntt1 = NTTPolynomialRingZq::from(&p1);
273        let ntt2 = NTTPolynomialRingZq::from(&p2);
274
275        ntt1.add_assign(&ntt2);
276
277        assert_eq!(&p1 + &p2, PolynomialRingZq::from(ntt1))
278    }
279
280    /// Ensures that the function panics for differing moduli.
281    #[test]
282    #[should_panic]
283    fn different_moduli() {
284        let mut modulus0 = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
285        modulus0.set_ntt_unchecked(64);
286        let mut modulus1 = ModulusPolynomialRingZq::from_str("6  1 0 0 0 0 1 mod 257").unwrap();
287        modulus1.set_ntt_unchecked(64);
288
289        let mut a = NTTPolynomialRingZq::sample_uniform(&modulus0);
290        let b = NTTPolynomialRingZq::sample_uniform(&modulus1);
291
292        a += b;
293    }
294}
qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/add.rs

qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
add.rs
