qfall_math/integer_mod_q/mat_polynomial_ring_zq/
coefficient_embedding.rs

1// Copyright © 2025 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//! This module contains implementations to transform a [`MatPolynomialRingZq`]
10//! into a [`MatZq`] and a [`ModulusPolynomialRingZq`] and reverse by using the coefficient embedding.
11
12use super::MatPolynomialRingZq;
13use crate::{
14    integer::{PolyOverZ, Z},
15    integer_mod_q::{MatZq, ModulusPolynomialRingZq},
16    traits::{
17        FromCoefficientEmbedding, GetCoefficient, IntoCoefficientEmbedding, MatrixDimensions,
18        MatrixGetEntry, MatrixSetEntry, SetCoefficient,
19    },
20};
21
22impl IntoCoefficientEmbedding<(MatZq, ModulusPolynomialRingZq)> for &MatPolynomialRingZq {
23    /// Computes the coefficient embedding of a matrix of polynomials
24    /// in a [`MatZq`] and a [`ModulusPolynomialRingZq`].
25    /// Each column vector of polynomials is embedded into `size` many
26    /// row vectors of coefficients. The first one containing their
27    /// coefficients of degree 0, and the last one their coefficients
28    /// of degree `size - 1`.
29    /// It inverts the operation of [`MatPolynomialRingZq::from_coefficient_embedding`].
30    ///
31    /// The representation of the polynomials in the embedding is in the range `[0, modulus_polynomial)`.
32    ///
33    /// Parameters:
34    /// - `size`: determines the number of rows each polynomial is embedded in.
35    ///   It has to be larger than the degree of all polynomials.
36    ///
37    /// Returns a coefficient embedding as a matrix if `size` is large enough.
38    ///
39    /// # Examples
40    /// ```
41    /// use std::str::FromStr;
42    /// use qfall_math::{
43    ///     integer_mod_q::{MatZq, MatPolynomialRingZq},
44    ///     traits::IntoCoefficientEmbedding,
45    /// };
46    ///
47    /// let poly = MatPolynomialRingZq::from_str("[[1  1, 2  1 2],[1  -1, 2  -1 -2]] / 3  1 2 3 mod 17").unwrap();
48    /// let embedding = poly.into_coefficient_embedding(2);
49    /// let cmp_mat = MatZq::from_str("[[1, 1],[0, 2],[-1, -1],[0, -2]] mod 17").unwrap();
50    /// assert_eq!((cmp_mat, poly.get_mod()), embedding);
51    /// ```
52    ///
53    /// # Panics ...
54    /// - if `size` is not larger than the degree of the polynomial, i.e.
55    ///   not all coefficients can be embedded.
56    fn into_coefficient_embedding(self, size: impl Into<i64>) -> (MatZq, ModulusPolynomialRingZq) {
57        let size = size.into();
58        let num_rows = self.get_num_rows();
59        let num_columns = self.get_num_columns();
60
61        let mut out = MatZq::new(num_rows * size, num_columns, self.modulus.get_q());
62
63        for column in 0..num_columns {
64            for row in 0..num_rows {
65                let entry: PolyOverZ = unsafe { self.get_entry_unchecked(row, column) };
66                let length = entry.get_degree() + 1;
67                assert!(
68                    size >= length,
69                    "The matrix can not be embedded, as the length \
70                    of a polynomial ({length}) is larger than \
71                    the provided size ({size})."
72                );
73
74                for index in 0..size {
75                    let coeff: Z = unsafe { entry.get_coeff_unchecked(index) };
76                    out.set_entry(row * size + index, column, coeff).unwrap()
77                }
78            }
79        }
80
81        (out, self.get_mod())
82    }
83}
84
85impl FromCoefficientEmbedding<(&MatZq, &ModulusPolynomialRingZq, i64)> for MatPolynomialRingZq {
86    /// Computes a [`MatPolynomialRingZq`] from a coefficient embedding.
87    /// Interprets the first `degree + 1` many rows of the matrix as the
88    /// coefficients of the first row of polynomials. The first one containing
89    /// their coefficients of degree 0, and the last one their coefficients
90    /// of degree `degree`. It inverts the operation of
91    /// [`MatPolynomialRingZq::into_coefficient_embedding`](#method.into_coefficient_embedding).
92    ///
93    /// Parameters:
94    /// - `embedding`: the coefficient matrix, the modulus, and the maximal
95    ///   degree of the polynomials (defines how the matrix is split)
96    ///
97    /// Returns a row vector of polynomials that corresponds to the embedding.
98    ///
99    /// # Examples
100    /// ```
101    /// use std::str::FromStr;
102    /// use qfall_math::{
103    ///     integer_mod_q::{MatZq, MatPolynomialRingZq, ModulusPolynomialRingZq},
104    ///     traits::FromCoefficientEmbedding,
105    /// };
106    ///
107    /// let matrix = MatZq::from_str("[[17, 1],[3, 2],[-5, 3],[1, 2]] mod 19").unwrap();
108    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 2 3 4 mod 19").unwrap();
109    /// let mat = MatPolynomialRingZq::from_coefficient_embedding((&matrix, &modulus, 1));
110    /// let cmp_mat = MatPolynomialRingZq::from_str("[[2  17 3, 2  1 2],[2  -5 1, 2  3 2]] / 4  1 2 3 4 mod 19").unwrap();
111    /// assert_eq!(cmp_mat, mat);
112    /// ```
113    ///
114    /// # Panics ...
115    /// - if `degree`+1 does not divide the number of rows of the embedding.
116    /// - if the moduli mismatch.
117    fn from_coefficient_embedding(embedding: (&MatZq, &ModulusPolynomialRingZq, i64)) -> Self {
118        let degree = embedding.2;
119        let num_rows = embedding.0.get_num_rows();
120        let num_columns = embedding.0.get_num_columns();
121
122        assert_eq!(
123            num_rows % (degree + 1),
124            0,
125            "The provided degree of polynomials ({degree}) +1 must divide the number of rows of the embedding ({num_rows})."
126        );
127        assert_eq!(
128            Z::from(embedding.0.get_mod()),
129            embedding.1.get_q(),
130            "This is no valid embedding, since the integer moduli of matrix and modulus mismatch."
131        );
132
133        let mut out = MatPolynomialRingZq::new(num_rows / (degree + 1), num_columns, embedding.1);
134
135        for row in 0..out.get_num_rows() {
136            for column in 0..num_columns {
137                let mut poly = PolyOverZ::default();
138                for index in 0..(degree + 1) {
139                    let coeff: Z = unsafe {
140                        embedding
141                            .0
142                            .get_entry_unchecked(row * (degree + 1) + index, column)
143                    };
144                    unsafe { poly.set_coeff_unchecked(index, coeff) };
145                }
146                out.set_entry(row, column, poly).unwrap();
147            }
148        }
149
150        out.reduce();
151        out
152    }
153}
154
155#[cfg(test)]
156mod test_into_coefficient_embedding {
157    use crate::{
158        integer_mod_q::{MatPolynomialRingZq, MatZq},
159        traits::{Concatenate, IntoCoefficientEmbedding},
160    };
161    use std::str::FromStr;
162
163    /// Ensure that the initialization of the identity matrix works.
164    #[test]
165    fn standard_basis() {
166        let standard_basis = MatPolynomialRingZq::from_str(
167            "[[1  1, 2  0 1, 3  0 0 1],[1  1, 2  0 1, 3  0 0 1]] / 4  1 2 3 4 mod 17",
168        )
169        .unwrap();
170
171        let basis = standard_basis.into_coefficient_embedding(3);
172
173        assert_eq!(
174            MatZq::identity(3, 3, 17)
175                .concat_vertical(&MatZq::identity(3, 3, 17))
176                .unwrap(),
177            basis.0
178        );
179
180        assert_eq!(standard_basis.get_mod(), basis.1);
181    }
182
183    /// Ensure that the initialization of the identity matrix works.
184    #[test]
185    fn standard_basis_vector() {
186        let standard_basis =
187            MatPolynomialRingZq::from_str("[[1  1, 2  0 1]] / 3  1 2 3 mod 17").unwrap();
188
189        let basis = standard_basis.into_coefficient_embedding(3);
190
191        assert_eq!((MatZq::identity(3, 2, 17), standard_basis.get_mod()), basis);
192    }
193
194    /// Ensure that the embedding works with large entries.
195    #[test]
196    fn large_entries() {
197        let poly = MatPolynomialRingZq::from_str(&format!(
198            "[[3  17 {} {}, 1  1],[1  1, 2  0 1]] / 4  1 2 3 4 mod {}",
199            i64::MAX,
200            i64::MIN,
201            u64::MAX
202        ))
203        .unwrap();
204
205        let matrix = poly.into_coefficient_embedding(3);
206
207        let cmp_matrix = MatZq::from_str(&format!(
208            "[[17, 1],[{}, 0],[{}, 0]] mod {}",
209            i64::MAX,
210            i64::MIN,
211            u64::MAX
212        ))
213        .unwrap()
214        .concat_vertical(&MatZq::identity(3, 2, u64::MAX))
215        .unwrap();
216        assert_eq!((cmp_matrix, poly.get_mod()), matrix);
217    }
218
219    /// Ensure that the embedding works with large entries.
220    #[test]
221    fn large_entries_vector() {
222        let poly = MatPolynomialRingZq::from_str(&format!(
223            "[[3  17 {} {}, 1  1]] / 4  1 2 3 4 mod {}",
224            i64::MAX,
225            i64::MIN,
226            u64::MAX
227        ))
228        .unwrap();
229
230        let matrix = poly.into_coefficient_embedding(3);
231
232        let cmp_matrix = MatZq::from_str(&format!(
233            "[[17, 1],[{}, 0],[{}, 0]] mod {}",
234            i64::MAX,
235            i64::MIN,
236            u64::MAX
237        ))
238        .unwrap();
239        assert_eq!((cmp_matrix, poly.get_mod()), matrix);
240    }
241
242    /// Ensure that the function panics if the provided size is too small.
243    #[test]
244    #[should_panic]
245    fn size_too_small() {
246        let poly =
247            MatPolynomialRingZq::from_str("[[3  17 5 7, 2  0 1],[1  1, 1  1]] / 4  1 2 3 4 mod 19")
248                .unwrap();
249
250        let _ = poly.into_coefficient_embedding(2);
251    }
252
253    /// Ensure that the function panics if the the provided size is too small.
254    #[test]
255    #[should_panic]
256    fn size_too_small_vector() {
257        let poly =
258            MatPolynomialRingZq::from_str("[[3  17 5 7, 2  0 1]] / 4  1 2 3 4 mod 19").unwrap();
259
260        let _ = poly.into_coefficient_embedding(2);
261    }
262}
263
264#[cfg(test)]
265mod test_from_coefficient_embedding {
266    use crate::integer_mod_q::{MatPolynomialRingZq, MatZq, ModulusPolynomialRingZq};
267    use crate::traits::FromCoefficientEmbedding;
268    use std::str::FromStr;
269
270    /// Ensure that the embedding works with large entries.
271    #[test]
272    fn large_entries() {
273        let matrix = MatZq::from_str(&format!(
274            "[[17, 0],[{}, -1],[{}, 0]] mod {}",
275            i64::MAX,
276            i64::MIN,
277            u64::MAX
278        ))
279        .unwrap();
280        let modulus =
281            ModulusPolynomialRingZq::from_str(&format!("4  1 2 3 4 mod {}", u64::MAX)).unwrap();
282
283        let poly = MatPolynomialRingZq::from_coefficient_embedding((&matrix, &modulus, 0));
284
285        let cmp_poly = MatPolynomialRingZq::from_str(&format!(
286            "[[1  17, 0],[1  {}, 1  -1],[1  {}, 0]] / 4  1 2 3 4 mod {}",
287            i64::MAX,
288            i64::MIN,
289            u64::MAX
290        ))
291        .unwrap();
292        assert_eq!(cmp_poly, poly);
293    }
294
295    /// Ensure that the embedding works with large entries.
296    #[test]
297    fn large_entries_vector() {
298        let matrix = MatZq::from_str(&format!(
299            "[[17, 0],[{}, -1],[{}, 0]] mod {}",
300            i64::MAX,
301            i64::MIN,
302            u64::MAX
303        ))
304        .unwrap();
305        let modulus =
306            ModulusPolynomialRingZq::from_str(&format!("4  1 2 3 4 mod {}", u64::MAX)).unwrap();
307
308        let poly = MatPolynomialRingZq::from_coefficient_embedding((&matrix, &modulus, 2));
309
310        let cmp_poly = MatPolynomialRingZq::from_str(&format!(
311            "[[3  17 {} {}, 2  0 -1]] / 4  1 2 3 4 mod {}",
312            i64::MAX,
313            i64::MIN,
314            u64::MAX
315        ))
316        .unwrap();
317        assert_eq!(cmp_poly, poly);
318    }
319
320    /// Ensure that the function panics if the provided degree +1 does not divide
321    /// the number of rows of the embedding.
322    #[test]
323    #[should_panic]
324    fn degree_not_dividing() {
325        let matrix = MatZq::from_str(&format!(
326            "[[17, 0],[{}, -1],[{}, 0]] mod {}",
327            i64::MAX,
328            i64::MIN,
329            u64::MAX
330        ))
331        .unwrap();
332        let modulus =
333            ModulusPolynomialRingZq::from_str(&format!("4  1 2 3 4 mod {}", u64::MAX)).unwrap();
334
335        let _ = MatPolynomialRingZq::from_coefficient_embedding((&matrix, &modulus, 1));
336    }
337
338    /// Ensure that the function panics if the moduli mismatch.
339    #[test]
340    #[should_panic]
341    fn mismatching_moduli() {
342        let matrix = MatZq::from_str(&format!(
343            "[[17, 0],[{}, -1],[{}, 0]] mod 17",
344            i64::MAX,
345            i64::MIN
346        ))
347        .unwrap();
348        let modulus =
349            ModulusPolynomialRingZq::from_str(&format!("4  1 2 3 4 mod {}", u64::MAX)).unwrap();
350
351        let _ = MatPolynomialRingZq::from_coefficient_embedding((&matrix, &modulus, 3));
352    }
353}
qfall_math/integer_mod_q/mat_polynomial_ring_zq/coefficient_embedding.rs

qfall_math/integer_mod_q/mat_polynomial_ring_zq/
coefficient_embedding.rs
