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

qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
add.rs
