qfall_math/integer_mod_q/polynomial_ring_zq/norm.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 includes functionality to compute several norms
10//! defined on polynomials.
11
12use super::PolynomialRingZq;
13use crate::{
14 integer::Z,
15 integer_mod_q::{Zq, fmpz_mod_helpers::length},
16 rational::Q,
17 traits::{GetCoefficient, Pow},
18};
19use std::cmp::max;
20
21impl PolynomialRingZq {
22 /// Returns the squared Euclidean norm or squared 2-norm of the given polynomial.
23 /// The squared Euclidean norm for a polynomial is obtained by treating the coefficients
24 /// of the polynomial as a vector and then applying the standard squared Euclidean norm.
25 ///
26 /// Each length of an entry in this vector is defined as the shortest distance
27 /// to the next zero representative modulo q.
28 ///
29 /// # Examples
30 /// ```
31 /// use qfall_math::{integer::Z, integer_mod_q::PolynomialRingZq};
32 /// use std::str::FromStr;
33 ///
34 /// let poly = PolynomialRingZq::from_str("3 1 2 3 / 4 1 2 3 1 mod 11").unwrap();
35 ///
36 /// let sqrd_2_norm = poly.norm_eucl_sqrd();
37 ///
38 /// // 1*1 + 2*2 + 3*3 = 14
39 /// assert_eq!(Z::from(14), sqrd_2_norm);
40 /// ```
41 pub fn norm_eucl_sqrd(&self) -> Z {
42 let mut res = Z::ZERO;
43 for i in 0..=self.get_degree() {
44 let coeff: Z = unsafe { self.get_coeff_unchecked(i) };
45
46 res += length(&coeff.value, &self.modulus.get_q_as_modulus().modulus.n[0])
47 .pow(2)
48 .unwrap();
49 }
50 res
51 }
52
53 /// Returns the Euclidean norm or 2-norm of the given polynomial.
54 /// The Euclidean norm for a polynomial is obtained by treating the coefficients
55 /// of the polynomial as a vector and then applying the standard Euclidean norm.
56 ///
57 /// Each length of an entry in this vector is defined as the shortest distance
58 /// to the next zero representative modulo q.
59 ///
60 /// # Examples
61 /// ```
62 /// use qfall_math::{rational::Q, integer_mod_q::PolynomialRingZq};
63 /// use std::str::FromStr;
64 ///
65 /// let poly = PolynomialRingZq::from_str("1 3 / 4 1 0 0 1 mod 7").unwrap();
66 /// println!("{poly}");
67 ///
68 /// let norm = poly.norm_eucl();
69 ///
70 /// // sqrt(3*3) = 3
71 /// assert_eq!(Q::from(3), norm);
72 /// ```
73 pub fn norm_eucl(&self) -> Q {
74 self.norm_eucl_sqrd().sqrt()
75 }
76
77 /// Returns the infinity norm or the maximal absolute value of a
78 /// coefficient of the given polynomial.
79 /// The infinity norm for a polynomial is obtained by treating the coefficients
80 /// of the polynomial as a vector and then applying the standard infinity norm.
81 ///
82 /// Each length of an entry in this vector is defined as the shortest distance
83 /// to the next zero representative modulo q.
84 ///
85 /// # Examples
86 /// ```
87 /// use qfall_math::{integer::Z, integer_mod_q::PolynomialRingZq};
88 /// use std::str::FromStr;
89 ///
90 /// let poly = PolynomialRingZq::from_str("3 1 2 4 / 4 1 2 3 1 mod 7").unwrap();
91 ///
92 /// let infty_norm = poly.norm_infty();
93 ///
94 /// // max coefficient is 4 = -3
95 /// assert_eq!(Z::from(3), infty_norm);
96 /// ```
97 pub fn norm_infty(&self) -> Z {
98 let mut res = Z::ZERO;
99
100 for i in 0..=self.get_degree() {
101 let coeff: Z = unsafe { self.get_coeff_unchecked(i) };
102 let len = length(&coeff.value, &self.modulus.get_q_as_modulus().modulus.n[0]);
103 res = max(res, len);
104 }
105 res
106 }
107
108 /// Outputs the hamming weight of `self`, i.e. it returns the number of
109 /// non-zero coefficients in the polynomial.
110 ///
111 /// # Examples
112 /// ```
113 /// use qfall_math::integer_mod_q::PolynomialRingZq;
114 /// use std::str::FromStr;
115 ///
116 /// let poly = PolynomialRingZq::from_str("3 1 7 3 / 4 1 0 0 1 mod 7").unwrap();
117 ///
118 /// let hamming_weight = poly.hamming_weight();
119 ///
120 /// assert_eq!(2, hamming_weight);
121 /// ```
122 pub fn hamming_weight(&self) -> i64 {
123 let mut hamming_weight = 0;
124 for i in 0..=self.get_degree() {
125 let coeff: Zq = unsafe { self.get_coeff_unchecked(i) };
126 if !coeff.is_zero() {
127 hamming_weight += 1;
128 }
129 }
130 hamming_weight
131 }
132}
133
134#[cfg(test)]
135mod test_norm_eucl_sqrd {
136 use super::Z;
137 use crate::integer_mod_q::PolynomialRingZq;
138 use std::str::FromStr;
139
140 /// Check whether the squared euclidean norm for polynomials
141 /// with small coefficients is calculated correctly
142 #[test]
143 fn poly_small_coefficient() {
144 let poly_1 = PolynomialRingZq::from_str("0 / 2 1 1 mod 11").unwrap();
145 let poly_2 = PolynomialRingZq::from_str("3 1 2 3 / 4 1 2 3 1 mod 11").unwrap();
146 let poly_3 = PolynomialRingZq::from_str("3 1 20 194 / 4 1 2 3 1 mod 195").unwrap();
147
148 assert_eq!(poly_1.norm_eucl_sqrd(), Z::ZERO);
149 assert_eq!(poly_2.norm_eucl_sqrd(), Z::from(14));
150 assert_eq!(poly_3.norm_eucl_sqrd(), Z::from(402));
151 }
152
153 /// Check whether the squared euclidean norm for polynomials
154 /// with small coefficients is calculated correctly
155 #[test]
156 fn poly_large_coefficient() {
157 let poly_1 =
158 PolynomialRingZq::from_str(&format!("1 {} / 2 1 1 mod {}", u64::MAX, u128::MAX))
159 .unwrap();
160 let poly_2 = PolynomialRingZq::from_str(&format!(
161 "3 {} {} {} / 4 1 2 3 1 mod {}",
162 u64::MAX,
163 i64::MIN,
164 i64::MAX,
165 u64::MAX - 58
166 ))
167 .unwrap();
168
169 assert_eq!(
170 poly_1.norm_eucl_sqrd(),
171 Z::from(u64::MAX) * Z::from(u64::MAX)
172 );
173 assert_eq!(
174 poly_2.norm_eucl_sqrd(),
175 Z::from(58) * Z::from(58)
176 + Z::from((u64::MAX - 1) / 2 - 57) * Z::from((u64::MAX - 1) / 2 - 57)
177 + Z::from((u64::MAX - 1) / 2 - 58) * Z::from((u64::MAX - 1) / 2 - 58)
178 );
179 }
180}
181
182#[cfg(test)]
183mod test_norm_infty {
184 use super::Z;
185 use crate::integer_mod_q::PolynomialRingZq;
186 use std::str::FromStr;
187
188 /// Check whether the infinity norm for polynomials
189 /// with small coefficients is calculated correctly
190 #[test]
191 fn poly_small_coefficient() {
192 let poly_1 = PolynomialRingZq::from_str("0 / 2 1 1 mod 11").unwrap();
193 let poly_2 = PolynomialRingZq::from_str("3 1 2 3 / 4 1 2 3 1 mod 5").unwrap();
194 let poly_3 = PolynomialRingZq::from_str("3 1 20 194 / 4 1 2 3 1 mod 195").unwrap();
195
196 assert_eq!(poly_1.norm_infty(), Z::ZERO);
197 assert_eq!(poly_2.norm_infty(), Z::from(2));
198 assert_eq!(poly_3.norm_infty(), Z::from(20));
199 }
200
201 /// Check whether the infinity norm for polynomials
202 /// with small coefficients is calculated correctly
203 #[test]
204 fn poly_large_coefficient() {
205 let poly_1 =
206 PolynomialRingZq::from_str(&format!("1 {} / 2 1 1 mod {}", u64::MAX, u128::MAX))
207 .unwrap();
208 let poly_2 = PolynomialRingZq::from_str(&format!(
209 "3 {} {} {} / 4 1 2 3 1 mod {}",
210 u64::MAX,
211 i64::MIN,
212 i64::MAX,
213 u64::MAX - 58
214 ))
215 .unwrap();
216
217 assert_eq!(poly_1.norm_infty(), Z::from(u64::MAX));
218 assert_eq!(poly_2.norm_infty(), Z::from((u64::MAX - 1) / 2 - 57));
219 }
220}
221
222#[cfg(test)]
223mod test_hamming_weight {
224 use super::PolynomialRingZq;
225 use std::str::FromStr;
226
227 /// Ensures that the hamming weight is computed correctly.
228 #[test]
229 fn hamming_weight() {
230 let poly0 = PolynomialRingZq::from_str("0 / 4 1 0 0 1 mod 3").unwrap();
231 let poly1 =
232 PolynomialRingZq::from_str("6 0 0 2 3 4 5 / 8 1 0 0 0 0 0 0 1 mod 5").unwrap();
233
234 let hw0 = poly0.hamming_weight();
235 let hw1 = poly1.hamming_weight();
236
237 assert_eq!(0, hw0);
238 assert_eq!(3, hw1);
239 }
240}