qfall_math/integer/mat_poly_over_z/
coefficient_embedding.rs

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

qfall_math/integer/mat_poly_over_z/
coefficient_embedding.rs
