qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
mul.rs

1// Copyright © 2025 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 multiplication 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_mul;
21use std::ops::{Mul, MulAssign};
22
23impl Mul for &NTTPolynomialRingZq {
24    type Output = NTTPolynomialRingZq;
25
26    /// Multiplies `self` with `other`.
27    ///
28    /// Paramters:
29    /// - `other`: specifies the NTT-representation of the polynomial to multiply to `self`
30    /// - `modulus`: defines the modulus `q`
31    ///
32    /// Returns the NTT-representation of the multiplication of `self` and `other`.
33    ///
34    /// # Example
35    /// ```
36    /// use qfall_math::integer_mod_q::{NTTPolynomialRingZq, ModulusPolynomialRingZq};
37    /// use std::str::FromStr;
38    /// let mut modulus = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
39    /// modulus.set_ntt_unchecked(64);
40    ///
41    /// let a = NTTPolynomialRingZq::sample_uniform(&modulus);
42    /// let b = NTTPolynomialRingZq::sample_uniform(&modulus);
43    ///
44    /// let c = a * b;
45    /// ```
46    ///
47    /// # Panics ...
48    /// - if the moduli are not equal.
49    fn mul(self, other: Self) -> Self::Output {
50        if !self.compare_base(other) {
51            panic!("{}", self.call_compare_base_error(other).unwrap());
52        }
53        let binding = &self.modulus.get_q_as_modulus();
54        let mod_q = binding.get_fmpz_mod_ctx_struct();
55
56        let mut res = Vec::with_capacity(self.poly.capacity());
57        for i in 0..self.poly.len() {
58            let mut z_i = Z::ZERO;
59            unsafe {
60                fmpz_mod_mul(
61                    &mut z_i.value,
62                    &self.poly[i].value,
63                    &other.poly[i].value,
64                    mod_q,
65                );
66            }
67            res.push(z_i)
68        }
69        Self::Output {
70            poly: res,
71            modulus: self.modulus.clone(),
72        }
73    }
74}
75
76arithmetic_trait_borrowed_to_owned!(
77    Mul,
78    mul,
79    NTTPolynomialRingZq,
80    NTTPolynomialRingZq,
81    NTTPolynomialRingZq
82);
83arithmetic_trait_mixed_borrowed_owned!(
84    Mul,
85    mul,
86    NTTPolynomialRingZq,
87    NTTPolynomialRingZq,
88    NTTPolynomialRingZq
89);
90
91impl MulAssign<&NTTPolynomialRingZq> for NTTPolynomialRingZq {
92    /// Multiplies `self` with `other` reusing the memory of `self`.
93    ///
94    /// Paramters:
95    /// - `other`: specifies the NTT-representation of the polynomial to multiply with `self`
96    ///
97    /// Computes the NTT-representation of the multiplication of `self` and `other`.
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 mul_assign(&mut self, other: &NTTPolynomialRingZq) {
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_mul(
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    MulAssign,
136    mul_assign,
137    NTTPolynomialRingZq,
138    NTTPolynomialRingZq
139);
140
141#[cfg(test)]
142mod test_mul {
143    use crate::{
144        integer_mod_q::{
145            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
146        },
147        traits::SetCoefficient,
148    };
149    use std::{ops::Mul, str::FromStr};
150
151    /// Ensure that the entrywise multiplication and the intuitive multiplication 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 ntt_res = ntt1.mul(ntt2);
173
174        assert_eq!(&p1 * &p2, PolynomialRingZq::from(ntt_res))
175    }
176
177    /// Ensure that the entrywise multiplication and the intuitive multiplication 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 ntt_res = ntt1.mul(&ntt2);
199
200        assert_eq!(&p1 * &p2, PolynomialRingZq::from(ntt_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_mul_assign {
221    use crate::{
222        integer_mod_q::{
223            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
224        },
225        traits::SetCoefficient,
226    };
227    use std::{ops::MulAssign, str::FromStr};
228
229    /// Ensure that the entrywise multiplication and the intuitive multiplication 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.mul_assign(ntt2);
251
252        assert_eq!(&p1 * &p2, PolynomialRingZq::from(ntt1))
253    }
254
255    /// Ensure that the entrywise multiplication and the intuitive multiplication 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.mul_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/mul.rs

qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
mul.rs
