qfall_math/integer_mod_q/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 [`PolynomialRingZq`]
10//! into a [`MatZq`] and a [`ModulusPolynomialRingZq`] and reverse by using the coefficient embedding.
11
12use crate::{
13 integer::Z,
14 integer_mod_q::{MatZq, ModulusPolynomialRingZq, PolynomialRingZq},
15 traits::{
16 FromCoefficientEmbedding, GetCoefficient, IntoCoefficientEmbedding, MatrixDimensions,
17 MatrixGetEntry, MatrixSetEntry, SetCoefficient,
18 },
19};
20
21impl IntoCoefficientEmbedding<(MatZq, ModulusPolynomialRingZq)> for &PolynomialRingZq {
22 /// Computes the coefficient embedding of the polynomial
23 /// in a [`MatZq`] as a column vector, where the i-th entry
24 /// of the vector corresponds to the i-th coefficient, and a
25 /// [`ModulusPolynomialRingZq`].
26 /// It inverts the operation of [`PolynomialRingZq::from_coefficient_embedding`].
27 ///
28 /// The representation of the polynomials in the embedding is in the range `[0, modulus_polynomial)`.
29 ///
30 /// Parameters:
31 /// - `size`: determines the number of rows of the embedding. It has to be larger
32 /// than the degree of the polynomial.
33 ///
34 /// Returns a coefficient embedding as a column vector if `size` is large enough.
35 ///
36 /// # Examples
37 /// ```
38 /// use std::str::FromStr;
39 /// use qfall_math::{
40 /// integer_mod_q::{MatZq, PolynomialRingZq},
41 /// traits::IntoCoefficientEmbedding,
42 /// };
43 ///
44 /// let poly = PolynomialRingZq::from_str("2 1 -2 / 3 17 3 5 mod 19").unwrap();
45 /// let embedding = poly.into_coefficient_embedding(3);
46 /// let cmp_vector = MatZq::from_str("[[1],[-2],[0]] mod 19").unwrap();
47 /// assert_eq!((cmp_vector, poly.get_mod()), embedding);
48 /// ```
49 ///
50 /// # Panics ...
51 /// - if `size` is not larger than the degree of the polynomial, i.e.
52 /// not all coefficients can be embedded.
53 fn into_coefficient_embedding(self, size: impl Into<i64>) -> (MatZq, ModulusPolynomialRingZq) {
54 let size = size.into();
55 let length = self.get_degree() + 1;
56 assert!(
57 size >= length,
58 "The polynomial can not be embedded in the vector, \
59 as the length of the polynomial ({length}) is larger than \
60 the provided size ({size})."
61 );
62 let mut out = MatZq::new(size, 1, self.modulus.get_q());
63 for j in 0..size {
64 let coeff: Z = unsafe { self.get_coeff_unchecked(j) };
65 unsafe { out.set_entry_unchecked(j, 0, coeff) };
66 }
67
68 (out, self.modulus.clone())
69 }
70}
71
72impl FromCoefficientEmbedding<(&MatZq, &ModulusPolynomialRingZq)> for PolynomialRingZq {
73 /// Computes a polynomial of degree `n-1` from a column vector of size `n` and a modulus.
74 /// The i-th entry of the column vector is taken
75 /// as the i-th coefficient of the polynomial.
76 /// It inverts the operation of
77 /// [`PolynomialRingZq::into_coefficient_embedding`](#method.into_coefficient_embedding).
78 ///
79 /// Parameters:
80 /// - `embedding`: the column vector that encodes the embedding and the modulus of the resulting polynomial
81 ///
82 /// Returns a polynomial that corresponds to the embedding.
83 ///
84 /// # Examples
85 /// ```
86 /// use std::str::FromStr;
87 /// use qfall_math::{
88 /// integer_mod_q::{MatZq, PolynomialRingZq, ModulusPolynomialRingZq},
89 /// traits::FromCoefficientEmbedding,
90 /// };
91 ///
92 /// let vector = MatZq::from_str("[[17],[3],[-5]] mod 19").unwrap();
93 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 2 3 4 mod 19").unwrap();
94 /// let poly = PolynomialRingZq::from_coefficient_embedding((&vector, &modulus));
95 /// let cmp_poly = PolynomialRingZq::from_str("3 17 3 -5 / 4 1 2 3 4 mod 19").unwrap();
96 /// assert_eq!(cmp_poly, poly);
97 /// ```
98 ///
99 /// # Panics ...
100 /// - if the provided embedding is not a column vector.
101 /// - if the moduli mismatch.
102 fn from_coefficient_embedding(embedding: (&MatZq, &ModulusPolynomialRingZq)) -> Self {
103 assert!(
104 embedding.0.is_column_vector(),
105 "This is no valid embedding, since the matrix is no column vector."
106 );
107 assert_eq!(
108 Z::from(embedding.0.get_mod()),
109 embedding.1.get_q(),
110 "This is no valid embedding, since the integer moduli of matrix and modulus mismatch."
111 );
112 let mut out = PolynomialRingZq::from((0, embedding.1));
113 for i in 0..embedding.0.get_num_rows() {
114 let entry: Z = unsafe { embedding.0.get_entry_unchecked(i, 0) };
115 unsafe { out.set_coeff_unchecked(i, entry) }
116 }
117 out
118 }
119}
120
121#[cfg(test)]
122mod test_into_coefficient_embedding {
123 use crate::{
124 integer_mod_q::{MatZq, PolynomialRingZq},
125 traits::IntoCoefficientEmbedding,
126 };
127 use std::str::FromStr;
128
129 /// Ensure that the embedding works with large entries.
130 #[test]
131 fn large_entries() {
132 let poly = PolynomialRingZq::from_str(&format!(
133 "3 17 {} {} / 4 1 2 3 4 mod {}",
134 i64::MAX,
135 i64::MIN,
136 u64::MAX
137 ))
138 .unwrap();
139
140 let embedding = poly.into_coefficient_embedding(3);
141
142 let cmp_vector = MatZq::from_str(&format!(
143 "[[17],[{}],[{}]] mod {}",
144 i64::MAX,
145 i64::MIN,
146 u64::MAX
147 ))
148 .unwrap();
149 assert_eq!((cmp_vector, poly.modulus), embedding);
150 }
151
152 /// Ensure that zero is embedded correctly.
153 #[test]
154 fn test_zero() {
155 let poly = PolynomialRingZq::from_str("0 / 3 17 3 5 mod 19").unwrap();
156 let embedding = poly.into_coefficient_embedding(1);
157
158 let cmp_vector = MatZq::from_str("[[0]] mod 19").unwrap();
159 assert_eq!((cmp_vector, poly.get_mod()), embedding);
160 }
161
162 /// Ensure that the function panics if the the provided size is too small.
163 #[test]
164 #[should_panic]
165 fn size_too_small() {
166 let poly = PolynomialRingZq::from_str("3 17 1 2 / 4 1 2 3 4 mod 19").unwrap();
167
168 let _ = poly.into_coefficient_embedding(2);
169 }
170}
171
172#[cfg(test)]
173mod test_from_coefficient_embedding {
174 use crate::{
175 integer_mod_q::{MatZq, ModulusPolynomialRingZq, PolynomialRingZq},
176 traits::FromCoefficientEmbedding,
177 };
178 use std::str::FromStr;
179
180 /// Ensure that the embedding works with large entries.
181 #[test]
182 fn large_entries() {
183 let vector = MatZq::from_str(&format!(
184 "[[17],[{}],[{}]] mod {}",
185 i64::MAX,
186 i64::MIN,
187 u64::MAX
188 ))
189 .unwrap();
190 let modulus =
191 ModulusPolynomialRingZq::from_str(&format!("4 1 2 3 4 mod {}", u64::MAX)).unwrap();
192
193 let poly = PolynomialRingZq::from_coefficient_embedding((&vector, &modulus));
194
195 let cmp_poly = PolynomialRingZq::from_str(&format!(
196 "3 17 {} {} / 4 1 2 3 4 mod {}",
197 i64::MAX,
198 i64::MIN,
199 u64::MAX
200 ))
201 .unwrap();
202 assert_eq!(cmp_poly, poly);
203 }
204
205 /// Ensure that the function panics if the provided matrix is not a column vector.
206 #[test]
207 #[should_panic]
208 fn not_column_vector() {
209 let vector = MatZq::from_str("[[17, 1],[-17, -1],[5, 9]] mod 42").unwrap();
210 let modulus = ModulusPolynomialRingZq::from_str("4 1 2 3 4 mod 42").unwrap();
211
212 let _ = PolynomialRingZq::from_coefficient_embedding((&vector, &modulus));
213 }
214
215 /// Ensure that the function panics if the moduli mismatch.
216 #[test]
217 #[should_panic]
218 fn mismatching_moduli() {
219 let vector = MatZq::from_str("[[17],[-1],[9]] mod 42").unwrap();
220 let modulus = ModulusPolynomialRingZq::from_str("4 1 2 3 4 mod 33").unwrap();
221
222 let _ = PolynomialRingZq::from_coefficient_embedding((&vector, &modulus));
223 }
224}