qfall_math/integer/mat_poly_over_z/arithmetic/
mul.rs

1// Copyright © 2023 Phil Milewski, Marcel Luca Schmidt
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 the [`Mul`] trait for [`MatPolyOverZ`] values.
10
11use super::super::MatPolyOverZ;
12use crate::error::MathError;
13use crate::integer_mod_q::MatPolynomialRingZq;
14use crate::macros::arithmetics::{
15    arithmetic_trait_borrowed_to_owned, arithmetic_trait_mixed_borrowed_owned,
16};
17use crate::traits::MatrixDimensions;
18use flint_sys::fmpz_poly_mat::fmpz_poly_mat_mul_KS;
19use std::ops::Mul;
20
21impl Mul for &MatPolyOverZ {
22    type Output = MatPolyOverZ;
23
24    /// Implements the [`Mul`] trait for two [`MatPolyOverZ`] values.
25    /// [`Mul`] is implemented for any combination of [`MatPolyOverZ`] and borrowed [`MatPolyOverZ`].
26    ///
27    /// Parameters:
28    /// - `other`: specifies the value to multiply with `self`
29    ///
30    /// Returns the product of `self` and `other` as a [`MatPolyOverZ`].
31    ///
32    /// # Examples
33    /// ```
34    /// use qfall_math::integer::MatPolyOverZ;
35    /// use std::str::FromStr;
36    ///
37    /// let a: MatPolyOverZ = MatPolyOverZ::from_str("[[0, 1  42, 2  42 24],[3  17 24 42, 1  17, 1  42]]").unwrap();
38    /// let b: MatPolyOverZ = MatPolyOverZ::from_str("[[1  -42, 2  24 42],[1  -1, 1  17],[0, 2  1 42]]").unwrap();
39    ///
40    /// let c = &a * &b;
41    /// let d = a * b;
42    /// let e = &c * d;
43    /// let f = c * &e;
44    /// ```
45    ///
46    /// # Panics ...
47    /// - if the dimensions of `self` and `other` do not match for multiplication.
48    fn mul(self, other: Self) -> Self::Output {
49        self.mul_safe(other).unwrap()
50    }
51}
52
53impl Mul<&MatPolynomialRingZq> for &MatPolyOverZ {
54    type Output = MatPolynomialRingZq;
55    /// Implements the [`Mul`] trait for a [`MatPolyOverZ`] matrix with a [`MatPolynomialRingZq`] matrix.
56    /// [`Mul`] is implemented for any combination of owned and borrowed values.
57    ///
58    /// Parameters:
59    /// - `other`: specifies the value to multiply with `self`
60    ///
61    /// Returns the product of `self` and `other` as a [`MatPolynomialRingZq`].
62    ///
63    /// # Examples
64    /// ```
65    /// use qfall_math::integer_mod_q::MatPolynomialRingZq;
66    /// use qfall_math::integer::MatPolyOverZ;
67    /// use std::str::FromStr;
68    ///
69    /// let mat_1 = MatPolyOverZ::from_str("[[2  1 42, 1  17],[1  8, 2  5 6]]").unwrap();
70    /// let mat_2 = MatPolynomialRingZq::from_str("[[2  1 42, 1  17],[1  8, 2  5 6]] / 3  1 2 3 mod 17").unwrap();
71    ///
72    /// let mat_3 = &mat_1 * &mat_2;
73    /// ```
74    ///
75    /// # Panics ...
76    /// - if the dimensions of `self` and `other` do not match for multiplication.
77    fn mul(self, other: &MatPolynomialRingZq) -> Self::Output {
78        self.mul_mat_poly_ring_zq_safe(other).unwrap()
79    }
80}
81
82arithmetic_trait_borrowed_to_owned!(
83    Mul,
84    mul,
85    MatPolyOverZ,
86    MatPolynomialRingZq,
87    MatPolynomialRingZq
88);
89arithmetic_trait_mixed_borrowed_owned!(
90    Mul,
91    mul,
92    MatPolyOverZ,
93    MatPolynomialRingZq,
94    MatPolynomialRingZq
95);
96
97impl MatPolyOverZ {
98    /// Implements multiplication for two [`MatPolyOverZ`] values.
99    ///
100    /// Parameters:
101    /// - `other`: specifies the value to multiply with `self`
102    ///
103    /// Returns the product of `self` and `other` as a [`MatPolyOverZ`]
104    /// or an error if the dimensions of `self` and `other` do not match for multiplication.
105    ///
106    /// # Examples
107    /// ```
108    /// use qfall_math::integer::MatPolyOverZ;
109    /// use std::str::FromStr;
110    ///
111    /// let a: MatPolyOverZ = MatPolyOverZ::from_str("[[0, 2  42 24],[3  17 24 42, 1  17]]").unwrap();
112    /// let b: MatPolyOverZ = MatPolyOverZ::from_str("[[1  -42, 2  24 42],[3  1 12 4, 1  17]]").unwrap();
113    ///
114    /// let c: MatPolyOverZ = a.mul_safe(&b).unwrap();
115    /// ```
116    ///
117    /// # Errors and Failures
118    /// - Returns a [`MathError`] of type
119    ///   [`MathError::MismatchingMatrixDimension`] if the dimensions of `self`
120    ///   and `other` do not match for multiplication.
121    pub fn mul_safe(&self, other: &Self) -> Result<Self, MathError> {
122        if self.get_num_columns() != other.get_num_rows() {
123            return Err(MathError::MismatchingMatrixDimension(format!(
124                "Tried to multiply a '{}x{}' matrix and a '{}x{}' matrix.",
125                self.get_num_rows(),
126                self.get_num_columns(),
127                other.get_num_rows(),
128                other.get_num_columns()
129            )));
130        }
131
132        let mut new = MatPolyOverZ::new(self.get_num_rows(), other.get_num_columns());
133        // Testing shows that `fmpz_poly_mat_mul_KS` should almost always be more efficient for parameter sets
134        // relevant in lattice-based crypto than `fmpz_poly_mat_mul_classical`. Thus, we can spare ourselves
135        // the evaluation time in `fmpz_poly_mat_mul` to determine which algorithm performs better
136        unsafe { fmpz_poly_mat_mul_KS(&mut new.matrix, &self.matrix, &other.matrix) };
137        Ok(new)
138    }
139
140    /// Implements multiplication for a [`MatPolyOverZ`] matrix with a [`MatPolynomialRingZq`]  matrix.
141    ///
142    /// Parameters:
143    /// - `other`: specifies the value to multiply with `self`
144    ///
145    /// Returns the product of `self` and `other` as a [`MatPolynomialRingZq`].
146    ///
147    /// # Examples
148    /// ```
149    /// use qfall_math::integer_mod_q::MatPolynomialRingZq;
150    /// use qfall_math::integer::MatPolyOverZ;
151    /// use std::str::FromStr;
152    ///
153    /// let mat_1 = MatPolyOverZ::from_str("[[2  1 42, 1  17],[1  8, 2  5 6]]").unwrap();
154    /// let mat_2 = MatPolynomialRingZq::from_str("[[2  1 42, 1  17],[1  8, 2  5 6]] / 3  1 2 3 mod 17").unwrap();
155    ///
156    /// let mat_3 = &mat_1.mul_mat_poly_ring_zq_safe(&mat_2).unwrap();
157    /// ```
158    ///
159    /// # Errors and Failures
160    /// - Returns a [`MathError`] of type
161    ///   [`MathError::MismatchingMatrixDimension`] if the dimensions of `self`
162    ///   and `other` do not match for multiplication.
163    pub fn mul_mat_poly_ring_zq_safe(
164        &self,
165        other: &MatPolynomialRingZq,
166    ) -> Result<MatPolynomialRingZq, MathError> {
167        let mut out =
168            MatPolynomialRingZq::new(self.get_num_rows(), self.get_num_columns(), other.get_mod());
169
170        out.matrix = self.mul_safe(&other.matrix)?;
171        out.reduce();
172
173        Ok(out)
174    }
175}
176
177arithmetic_trait_borrowed_to_owned!(Mul, mul, MatPolyOverZ, MatPolyOverZ, MatPolyOverZ);
178arithmetic_trait_mixed_borrowed_owned!(Mul, mul, MatPolyOverZ, MatPolyOverZ, MatPolyOverZ);
179
180#[cfg(test)]
181mod test_mul {
182    use super::MatPolyOverZ;
183    use std::str::FromStr;
184
185    /// Checks if matrix multiplication works fine for squared matrices
186    #[test]
187    fn square_correctness() {
188        let mat_1 = MatPolyOverZ::from_str("[[2  0 1, 1  4],[0, 3  1 2 3]]").unwrap();
189        let mat_2 = MatPolyOverZ::from_str("[[2  0 1, 1  4],[0, 3  1 2 3]]").unwrap();
190        let res = MatPolyOverZ::from_str("[[3  0 0 1, 3  4 12 12],[0, 5  1 4 10 12 9]]").unwrap();
191        assert_eq!(res, &mat_1 * &mat_2);
192    }
193
194    /// Checks if matrix multiplication works fine for matrices of different dimensions
195    #[test]
196    fn different_dimensions_correctness() {
197        let mat = MatPolyOverZ::from_str("[[2  1 4, 1  7],[1  3, 3  12 3 4]]").unwrap();
198        let vec = MatPolyOverZ::from_str("[[1  4],[0]]").unwrap();
199        let cmp = MatPolyOverZ::from_str("[[2  4 16],[1  12]]").unwrap();
200
201        assert_eq!(cmp, &mat * &vec);
202    }
203
204    /// Checks if matrix multiplication works fine for large entries
205    #[test]
206    fn large_entries() {
207        let mat =
208            MatPolyOverZ::from_str(&format!("[[2  3 {}, 1  15],[1  1, 0]]", u64::MAX)).unwrap();
209        let vec = MatPolyOverZ::from_str(&format!("[[2  1 {}],[0]]", u64::MAX)).unwrap();
210        let cmp = MatPolyOverZ::from_str(&format!(
211            "[[3  3 {} {}],[2  1 {}]]",
212            u128::from(u64::MAX) * 4,
213            u128::from(u64::MAX) * u128::from(u64::MAX),
214            u64::MAX
215        ))
216        .unwrap();
217        assert_eq!(cmp, mat * vec);
218    }
219
220    /// Checks if matrix multiplication with incompatible matrix dimensions
221    /// throws an error as expected
222    #[test]
223    fn incompatible_dimensions() {
224        let a: MatPolyOverZ = MatPolyOverZ::from_str("[[2  0 1, 1  4],[0, 3  1 2 3]]").unwrap();
225        let b: MatPolyOverZ = MatPolyOverZ::from_str("[[2  0 1, 1  4]]").unwrap();
226        let c: MatPolyOverZ =
227            MatPolyOverZ::from_str("[[2  0 1, 1  4, 0],[0, 3  1 2 3, 1  3]]").unwrap();
228        assert!(a.mul_safe(&b).is_err());
229        assert!(c.mul_safe(&b).is_err());
230    }
231}
232
233#[cfg(test)]
234mod test_mul_mat_poly_over_z {
235    use super::MatPolynomialRingZq;
236    use crate::{integer::MatPolyOverZ, integer_mod_q::ModulusPolynomialRingZq};
237    use std::str::FromStr;
238
239    /// Checks whether multiplication is available for other types.
240    #[test]
241    fn availability() {
242        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
243        let poly_mat = MatPolyOverZ::from_str("[[3  0 1 1, 1  3],[0, 2  1 2]]").unwrap();
244        let poly_ring_mat = MatPolynomialRingZq::from((&poly_mat, &modulus));
245
246        let _ = &poly_mat * &poly_ring_mat;
247        let _ = &poly_mat * poly_ring_mat.clone();
248        let _ = poly_mat.clone() * &poly_ring_mat;
249        let _ = poly_mat.clone() * poly_ring_mat.clone();
250    }
251
252    /// Checks if matrix multiplication works fine for matrices of different dimensions.
253    #[test]
254    fn different_dimensions_correctness() {
255        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
256        let poly_mat_1 = MatPolyOverZ::from_str("[[1  42],[1  17]]").unwrap();
257        let poly_ring_mat_1 = MatPolynomialRingZq::from((&poly_mat_1, &modulus));
258        let poly_mat_2 = MatPolyOverZ::from_str("[[4  -1 0 1 1, 1  42],[0, 2  1 2]]").unwrap();
259
260        let poly_ring_mat_3 = &poly_mat_2 * &poly_ring_mat_1;
261
262        let poly_mat_cmp = MatPolyOverZ::from_str("[[3  1 0 8],[0]]").unwrap();
263        let poly_ring_mat_cmp = MatPolynomialRingZq::from((&poly_mat_cmp, &modulus));
264
265        assert_eq!(poly_ring_mat_cmp, poly_ring_mat_3);
266    }
267
268    /// Checks if matrix multiplication with incompatible matrix dimensions
269    /// throws an error as expected.
270    #[test]
271    fn errors() {
272        let modulus_1 = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
273        let poly_mat_1 = MatPolyOverZ::from_str("[[4  -1 0 1 1],[2  1 2]]").unwrap();
274        let poly_ring_mat_1 = MatPolynomialRingZq::from((&poly_mat_1, &modulus_1));
275
276        assert!((poly_mat_1.mul_mat_poly_ring_zq_safe(&poly_ring_mat_1)).is_err());
277    }
278
279    /// Checks if multiplication panics if dimensions mismatch.
280    #[test]
281    #[should_panic]
282    fn mul_panic() {
283        let modulus1 = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
284        let poly_mat1 = MatPolyOverZ::from_str("[[1  3],[2  1 2]]").unwrap();
285        let poly_ring_mat1 = MatPolynomialRingZq::from((&poly_mat1, &modulus1));
286
287        let _ = &poly_mat1 * &poly_ring_mat1;
288    }
289}
qfall_math/integer/mat_poly_over_z/arithmetic/mul.rs

qfall_math/integer/mat_poly_over_z/arithmetic/
mul.rs
