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 mod_q = &self.modulus.get_fq_ctx().ctxp[0];
54
55        let mut res = Vec::with_capacity(self.poly.capacity());
56        for i in 0..self.poly.len() {
57            let mut z_i = Z::ZERO;
58            unsafe {
59                fmpz_mod_mul(
60                    &mut z_i.value,
61                    &self.poly[i].value,
62                    &other.poly[i].value,
63                    mod_q,
64                );
65            }
66            res.push(z_i)
67        }
68        Self::Output {
69            poly: res,
70            modulus: self.modulus.clone(),
71        }
72    }
73}
74
75arithmetic_trait_borrowed_to_owned!(
76    Mul,
77    mul,
78    NTTPolynomialRingZq,
79    NTTPolynomialRingZq,
80    NTTPolynomialRingZq
81);
82arithmetic_trait_mixed_borrowed_owned!(
83    Mul,
84    mul,
85    NTTPolynomialRingZq,
86    NTTPolynomialRingZq,
87    NTTPolynomialRingZq
88);
89
90impl MulAssign<&NTTPolynomialRingZq> for NTTPolynomialRingZq {
91    /// Multiplies `self` with `other` reusing the memory of `self`.
92    ///
93    /// Paramters:
94    /// - `other`: specifies the NTT-representation of the polynomial to multiply with `self`
95    ///
96    /// Computes the NTT-representation of the multiplication 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 mul_assign(&mut self, other: &NTTPolynomialRingZq) {
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_mul(
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    MulAssign,
134    mul_assign,
135    NTTPolynomialRingZq,
136    NTTPolynomialRingZq
137);
138
139#[cfg(test)]
140mod test_mul {
141    use crate::{
142        integer_mod_q::{
143            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
144        },
145        traits::SetCoefficient,
146    };
147    use std::{ops::Mul, str::FromStr};
148
149    /// Ensure that the entrywise multiplication and the intuitive multiplication 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 ntt_res = ntt1.mul(ntt2);
171
172        assert_eq!(&p1 * &p2, PolynomialRingZq::from(ntt_res))
173    }
174
175    /// Ensure that the entrywise multiplication and the intuitive multiplication 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 ntt_res = ntt1.mul(&ntt2);
197
198        assert_eq!(&p1 * &p2, PolynomialRingZq::from(ntt_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_mul_assign {
219    use crate::{
220        integer_mod_q::{
221            ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq, PolynomialRingZq,
222        },
223        traits::SetCoefficient,
224    };
225    use std::{ops::MulAssign, str::FromStr};
226
227    /// Ensure that the entrywise multiplication and the intuitive multiplication 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.mul_assign(ntt2);
249
250        assert_eq!(&p1 * &p2, PolynomialRingZq::from(ntt1))
251    }
252
253    /// Ensure that the entrywise multiplication and the intuitive multiplication 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.mul_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/mul.rs

qfall_math/integer_mod_q/ntt_polynomial_ring_zq/arithmetic/
mul.rs
