qfall_math/integer/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 [`PolyOverZ`]
10//! into a [`MatZ`] and reverse by using the coefficient embedding.
11
12use crate::{
13    integer::{MatZ, PolyOverZ},
14    traits::{
15        FromCoefficientEmbedding, GetCoefficient, IntoCoefficientEmbedding, MatrixDimensions,
16        MatrixGetEntry, MatrixSetEntry, SetCoefficient,
17    },
18};
19
20impl IntoCoefficientEmbedding<MatZ> for &PolyOverZ {
21    /// Computes the coefficient embedding of the polynomial
22    /// in a [`MatZ`] as a column vector, where the i-th entry
23    /// of the vector corresponds to the i-th coefficient.
24    /// It inverts the operation of [`PolyOverZ::from_coefficient_embedding`].
25    ///
26    /// Parameters:
27    /// - `size`: determines the number of rows of the embedding. It has to be larger
28    ///   than the degree of the polynomial.
29    ///
30    /// Returns a coefficient embedding as a column vector if `size` is large enough.
31    ///
32    /// # Examples
33    /// ```
34    /// use std::str::FromStr;
35    /// use qfall_math::{
36    ///     integer::{MatZ, PolyOverZ},
37    ///     traits::IntoCoefficientEmbedding,
38    /// };
39    ///
40    /// let poly = PolyOverZ::from_str("3  17 3 -5").unwrap();
41    /// let vector = poly.into_coefficient_embedding(4);
42    /// let cmp_vector = MatZ::from_str("[[17],[3],[-5],[0]]").unwrap();
43    /// assert_eq!(cmp_vector, vector);
44    /// ```
45    ///
46    /// # Panics ...
47    /// - if `size` is not larger than the degree of the polynomial, i.e.
48    ///   not all coefficients can be embedded.
49    fn into_coefficient_embedding(self, size: impl Into<i64>) -> MatZ {
50        let size = size.into();
51        let length = self.get_degree() + 1;
52        assert!(
53            size >= length,
54            "The polynomial can not be embedded in the vector, \
55            as the length of the polynomial ({length}) is larger than \
56            the provided size ({size})."
57        );
58        let mut out = MatZ::new(size, 1);
59        for j in 0..size {
60            let coeff = unsafe { self.get_coeff_unchecked(j) };
61            unsafe { out.set_entry_unchecked(j, 0, coeff) };
62        }
63
64        out
65    }
66}
67
68impl FromCoefficientEmbedding<&MatZ> for PolyOverZ {
69    /// Computes a polynomial from a vector.
70    /// The first i-th entry of the column vector is taken
71    /// as the coefficient of the polynomial.
72    /// It inverts the operation of
73    /// [`PolyOverZ::into_coefficient_embedding`](#method.into_coefficient_embedding).
74    ///
75    /// Parameters:
76    /// - `embedding`: the column vector that encodes the embedding
77    ///
78    /// Returns a polynomial that corresponds to the embedding.
79    ///
80    /// # Examples
81    /// ```
82    /// use std::str::FromStr;
83    /// use qfall_math::{
84    ///     integer::{MatZ, PolyOverZ},
85    ///     traits::FromCoefficientEmbedding,
86    /// };
87    ///
88    /// let vector = MatZ::from_str("[[17],[3],[-5]]").unwrap();
89    /// let poly = PolyOverZ::from_coefficient_embedding(&vector);
90    /// let cmp_poly = PolyOverZ::from_str("3  17 3 -5").unwrap();
91    /// assert_eq!(cmp_poly, poly);
92    /// ```
93    ///
94    /// # Panics ...
95    /// - if the provided embedding is not a column vector.
96    fn from_coefficient_embedding(embedding: &MatZ) -> Self {
97        assert!(
98            embedding.is_column_vector(),
99            "This is no valid embedding, since the matrix is no column vector."
100        );
101        let mut out = PolyOverZ::default();
102        for i in 0..embedding.get_num_rows() {
103            unsafe { out.set_coeff_unchecked(i, embedding.get_entry_unchecked(i, 0)) }
104        }
105        out
106    }
107}
108
109#[cfg(test)]
110mod test_into_coefficient_embedding {
111    use crate::{
112        integer::{MatZ, PolyOverZ},
113        traits::IntoCoefficientEmbedding,
114    };
115    use std::str::FromStr;
116
117    /// Ensure that the embedding works with large entries.
118    #[test]
119    fn large_entries() {
120        let poly = PolyOverZ::from_str(&format!("3  17 {} {}", i64::MAX, i64::MIN)).unwrap();
121
122        let vector = poly.into_coefficient_embedding(3);
123
124        let cmp_vector = MatZ::from_str(&format!("[[17],[{}],[{}]]", i64::MAX, i64::MIN)).unwrap();
125        assert_eq!(cmp_vector, vector);
126    }
127
128    /// Ensure that the function panics if the the provided size is too small.
129    #[test]
130    #[should_panic]
131    fn size_too_small() {
132        let poly = PolyOverZ::from_str("3  17 12 -1").unwrap();
133
134        let _ = poly.into_coefficient_embedding(2);
135    }
136}
137
138#[cfg(test)]
139mod test_from_coefficient_embedding {
140    use crate::{
141        integer::{MatZ, PolyOverZ},
142        traits::FromCoefficientEmbedding,
143    };
144    use std::str::FromStr;
145
146    /// Ensure that the embedding works with large entries.
147    #[test]
148    fn large_entries() {
149        let vector = MatZ::from_str(&format!("[[17],[{}],[{}]]", i64::MAX, i64::MIN)).unwrap();
150
151        let poly = PolyOverZ::from_coefficient_embedding(&vector);
152
153        let cmp_poly = PolyOverZ::from_str(&format!("3  17 {} {}", i64::MAX, i64::MIN)).unwrap();
154        assert_eq!(cmp_poly, poly);
155    }
156
157    /// Ensure that the function panics if the provided matrix is not a column vector.
158    #[test]
159    #[should_panic]
160    fn not_column_vector() {
161        let vector = MatZ::from_str("[[17, 1],[-17, -1],[5, 9]]").unwrap();
162
163        let _ = PolyOverZ::from_coefficient_embedding(&vector);
164    }
165}
qfall_math/integer/poly_over_z/coefficient_embedding.rs

qfall_math/integer/poly_over_z/
coefficient_embedding.rs
