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::fmpz_mod_helpers::length,
16 traits::{GetCoefficient, Pow},
17};
18use std::cmp::max;
19
20impl PolynomialRingZq {
21 /// Returns the squared Euclidean norm or squared 2-norm of the given polynomial.
22 /// The squared Euclidean norm for a polynomial is obtained by treating the coefficients
23 /// of the polynomial as a vector and then applying the standard squared Euclidean norm.
24 ///
25 /// Each length of an entry in this vector is defined as the shortest distance
26 /// to the next zero representative modulo q.
27 ///
28 /// # Examples
29 /// ```
30 /// use qfall_math::{integer::Z, integer_mod_q::PolynomialRingZq};
31 /// use std::str::FromStr;
32 ///
33 /// let poly = PolynomialRingZq::from_str("3 1 2 3 / 4 1 2 3 1 mod 11").unwrap();
34 ///
35 /// let sqrd_2_norm = poly.norm_eucl_sqrd();
36 ///
37 /// // 1*1 + 2*2 + 3*3 = 14
38 /// assert_eq!(Z::from(14), sqrd_2_norm);
39 /// ```
40 pub fn norm_eucl_sqrd(&self) -> Z {
41 let mut res = Z::ZERO;
42 for i in 0..=self.get_degree() {
43 let coeff: Z = unsafe { self.get_coeff_unchecked(i) };
44
45 res += length(&coeff.value, &self.modulus.get_q_as_modulus().modulus.n[0])
46 .pow(2)
47 .unwrap();
48 }
49 res
50 }
51
52 /// Returns the infinity norm or the maximal absolute value of a
53 /// coefficient of the given polynomial.
54 /// The infinity norm for a polynomial is obtained by treating the coefficients
55 /// of the polynomial as a vector and then applying the standard infinity 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::{integer::Z, integer_mod_q::PolynomialRingZq};
63 /// use std::str::FromStr;
64 ///
65 /// let poly = PolynomialRingZq::from_str("3 1 2 4 / 4 1 2 3 1 mod 7").unwrap();
66 ///
67 /// let infty_norm = poly.norm_infty();
68 ///
69 /// // max coefficient is 4 = -3
70 /// assert_eq!(Z::from(3), infty_norm);
71 /// ```
72 pub fn norm_infty(&self) -> Z {
73 let mut res = Z::ZERO;
74
75 for i in 0..=self.get_degree() {
76 let coeff: Z = unsafe { self.get_coeff_unchecked(i) };
77 let len = length(&coeff.value, &self.modulus.get_q_as_modulus().modulus.n[0]);
78 res = max(res, len);
79 }
80 res
81 }
82}
83
84#[cfg(test)]
85mod test_norm_eucl_sqrd {
86 use super::Z;
87 use crate::integer_mod_q::PolynomialRingZq;
88 use std::str::FromStr;
89
90 /// Check whether the squared euclidean norm for polynomials
91 /// with small coefficients is calculated correctly
92 #[test]
93 fn poly_small_coefficient() {
94 let poly_1 = PolynomialRingZq::from_str("0 / 2 1 1 mod 11").unwrap();
95 let poly_2 = PolynomialRingZq::from_str("3 1 2 3 / 4 1 2 3 1 mod 11").unwrap();
96 let poly_3 = PolynomialRingZq::from_str("3 1 20 194 / 4 1 2 3 1 mod 195").unwrap();
97
98 assert_eq!(poly_1.norm_eucl_sqrd(), Z::ZERO);
99 assert_eq!(poly_2.norm_eucl_sqrd(), Z::from(14));
100 assert_eq!(poly_3.norm_eucl_sqrd(), Z::from(402));
101 }
102
103 /// Check whether the squared euclidean norm for polynomials
104 /// with small coefficients is calculated correctly
105 #[test]
106 fn poly_large_coefficient() {
107 let poly_1 =
108 PolynomialRingZq::from_str(&format!("1 {} / 2 1 1 mod {}", u64::MAX, u128::MAX))
109 .unwrap();
110 let poly_2 = PolynomialRingZq::from_str(&format!(
111 "3 {} {} {} / 4 1 2 3 1 mod {}",
112 u64::MAX,
113 i64::MIN,
114 i64::MAX,
115 u64::MAX - 58
116 ))
117 .unwrap();
118
119 assert_eq!(
120 poly_1.norm_eucl_sqrd(),
121 Z::from(u64::MAX) * Z::from(u64::MAX)
122 );
123 assert_eq!(
124 poly_2.norm_eucl_sqrd(),
125 Z::from(58) * Z::from(58)
126 + Z::from((u64::MAX - 1) / 2 - 57) * Z::from((u64::MAX - 1) / 2 - 57)
127 + Z::from((u64::MAX - 1) / 2 - 58) * Z::from((u64::MAX - 1) / 2 - 58)
128 );
129 }
130}
131
132#[cfg(test)]
133mod test_norm_infty {
134 use super::Z;
135 use crate::integer_mod_q::PolynomialRingZq;
136 use std::str::FromStr;
137
138 /// Check whether the infinity norm for polynomials
139 /// with small coefficients is calculated correctly
140 #[test]
141 fn poly_small_coefficient() {
142 let poly_1 = PolynomialRingZq::from_str("0 / 2 1 1 mod 11").unwrap();
143 let poly_2 = PolynomialRingZq::from_str("3 1 2 3 / 4 1 2 3 1 mod 5").unwrap();
144 let poly_3 = PolynomialRingZq::from_str("3 1 20 194 / 4 1 2 3 1 mod 195").unwrap();
145
146 assert_eq!(poly_1.norm_infty(), Z::ZERO);
147 assert_eq!(poly_2.norm_infty(), Z::from(2));
148 assert_eq!(poly_3.norm_infty(), Z::from(20));
149 }
150
151 /// Check whether the infinity norm for polynomials
152 /// with small coefficients is calculated correctly
153 #[test]
154 fn poly_large_coefficient() {
155 let poly_1 =
156 PolynomialRingZq::from_str(&format!("1 {} / 2 1 1 mod {}", u64::MAX, u128::MAX))
157 .unwrap();
158 let poly_2 = PolynomialRingZq::from_str(&format!(
159 "3 {} {} {} / 4 1 2 3 1 mod {}",
160 u64::MAX,
161 i64::MIN,
162 i64::MAX,
163 u64::MAX - 58
164 ))
165 .unwrap();
166
167 assert_eq!(poly_1.norm_infty(), Z::from(u64::MAX));
168 assert_eq!(poly_2.norm_infty(), Z::from((u64::MAX - 1) / 2 - 57));
169 }
170}