qfall_math/integer_mod_q/mat_polynomial_ring_zq/norm.rs
1// Copyright 2025 Jan Niklas Siemer
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 matrices.
11
12use super::MatPolynomialRingZq;
13use crate::{
14 integer::{PolyOverZ, Z},
15 rational::Q,
16 traits::{MatrixDimensions, MatrixGetEntry, MatrixGetSubmatrix},
17};
18
19impl MatPolynomialRingZq {
20 /// Outputs the squared l_{2, ∞}-norm, i.e. it computes the squared Euclidean
21 /// norm of each column of the matrix and returns the largest one.
22 ///
23 /// # Examples
24 /// ```
25 /// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
26 /// use std::str::FromStr;
27 ///
28 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 7").unwrap();
29 /// let mat = MatPolyOverZ::from_str("[[1 2, 1 3],[1 2, 0]]").unwrap();
30 /// let mat = MatPolynomialRingZq::from((&mat, &modulus));
31 ///
32 /// let eucl_norm = mat.norm_l_2_infty_sqrd();
33 ///
34 /// // 3^2 + 0^2 = 9
35 /// assert_eq!(Z::from(9), eucl_norm);
36 /// ```
37 pub fn norm_l_2_infty_sqrd(&self) -> Z {
38 let mut max_sqrd_norm = Z::ZERO;
39 for i in 0..self.get_num_columns() {
40 let column = unsafe { self.get_column_unchecked(i) };
41 let sqrd_norm = column.norm_eucl_sqrd().unwrap();
42 if sqrd_norm > max_sqrd_norm {
43 max_sqrd_norm = sqrd_norm;
44 }
45 }
46 max_sqrd_norm
47 }
48
49 /// Outputs the l_{2, ∞}-norm, i.e. it computes the Euclidean
50 /// norm of each column of the matrix and returns the largest one.
51 ///
52 /// # Examples
53 /// ```
54 /// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
55 /// use std::str::FromStr;
56 /// # use qfall_math::rational::Q;
57 ///
58 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 5").unwrap();
59 /// let mat = MatPolyOverZ::from_str("[[1 2, 1 3],[1 2, 1 0],[1 3, 1 4],[1 3, 1 4]]").unwrap();
60 /// let mat = MatPolynomialRingZq::from((&mat, &modulus));
61 ///
62 /// let eucl_norm = mat.norm_l_2_infty();
63 ///
64 /// // sqrt(4 * 2^2) = 4
65 /// assert_eq!(Q::from(4), eucl_norm);
66 /// ```
67 pub fn norm_l_2_infty(&self) -> Q {
68 self.norm_l_2_infty_sqrd().sqrt()
69 }
70
71 /// Outputs the l_{∞, ∞}-norm, i.e. it computes the ∞-norm
72 /// of each column of the matrix and returns the largest one.
73 ///
74 /// # Examples
75 /// ```
76 /// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
77 /// use std::str::FromStr;
78 ///
79 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 7").unwrap();
80 /// let mat = MatPolyOverZ::from_str("[[1 2, 1 4],[1 2, 0]]").unwrap();
81 /// let mat = MatPolynomialRingZq::from((&mat, &modulus));
82 ///
83 /// let eucl_norm = mat.norm_l_infty_infty();
84 ///
85 /// // max{2, 3} = 3
86 /// assert_eq!(Z::from(3), eucl_norm);
87 /// ```
88 pub fn norm_l_infty_infty(&self) -> Z {
89 let mut max_norm = Z::ZERO;
90 for i in 0..self.get_num_columns() {
91 let column = unsafe { self.get_column_unchecked(i) };
92 let norm = column.norm_infty().unwrap();
93 if norm > max_norm {
94 max_norm = norm;
95 }
96 }
97 max_norm
98 }
99
100 /// Outputs the hamming weight of `self`, i.e. it computes the number of non-zero
101 /// coefficients across all polynomials in the matrix.
102 ///
103 /// # Examples
104 /// ```
105 /// use qfall_math::{integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq}, integer::{Z, MatPolyOverZ}};
106 /// use std::str::FromStr;
107 ///
108 /// let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 7").unwrap();
109 /// let mat = MatPolyOverZ::from_str("[[2 2 1, 2 3 0],[1 2, 0]]").unwrap();
110 /// let mat = MatPolynomialRingZq::from((&mat, &modulus));
111 ///
112 /// let hamming_weight = mat.hamming_weight();
113 ///
114 /// assert_eq!(4, hamming_weight);
115 /// ```
116 pub fn hamming_weight(&self) -> i64 {
117 let mut hamming_weight = 0;
118 for row in 0..self.get_num_rows() {
119 for col in 0..self.get_num_columns() {
120 let entry: PolyOverZ = unsafe { self.get_entry_unchecked(row, col) };
121 hamming_weight += entry.hamming_weight();
122 }
123 }
124 hamming_weight
125 }
126}
127
128#[cfg(test)]
129mod test_matrix_norms {
130 use super::{MatPolynomialRingZq, Q, Z};
131 use crate::{integer::MatPolyOverZ, integer_mod_q::ModulusPolynomialRingZq};
132 use std::str::FromStr;
133
134 /// Ensures that the squared l_{2, ∞}-norm is correctly computed.
135 #[test]
136 fn norm_sqrd_l_2_infty() {
137 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 9").unwrap();
138 let mat = MatPolyOverZ::from_str(
139 "[[1 3, 1 -2, 1 5],[1 -5, 1 -6, 2 1 1],[1 -4, 0, 0],[1 2, 0, 3 1 1 1]]",
140 )
141 .unwrap();
142 let mat = MatPolynomialRingZq::from((&mat, &modulus));
143
144 let sqrd_norm = mat.norm_l_2_infty_sqrd();
145
146 assert_eq!(Z::from(45), sqrd_norm);
147 }
148
149 /// Ensures that the l_{2, ∞}-norm is correctly computed.
150 #[test]
151 fn norm_l_2_infty() {
152 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 5").unwrap();
153 let mat =
154 MatPolyOverZ::from_str("[[1 -2, 4 -2 0 0 1],[1 -2, 1 -3],[1 -2, 0],[1 2, 0]]")
155 .unwrap();
156 let mat = MatPolynomialRingZq::from((&mat, &modulus));
157
158 let norm = mat.norm_l_2_infty();
159
160 assert_eq!(Q::from(4), norm);
161 }
162
163 /// Ensures that the l_{∞, ∞}-norm is correctly computed.
164 #[test]
165 fn norm_l_infty_infty() {
166 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 8").unwrap();
167 let mat = MatPolyOverZ::from_str("[[2 -2 1, 1 3],[1 2, 1 -5],[1 -2, 0]]").unwrap();
168 let mat = MatPolynomialRingZq::from((&mat, &modulus));
169
170 let infty_norm = mat.norm_l_infty_infty();
171
172 assert_eq!(Z::from(3), infty_norm);
173 }
174}
175
176#[cfg(test)]
177mod test_hamming_weight {
178 use super::MatPolynomialRingZq;
179 use crate::{integer::MatPolyOverZ, integer_mod_q::ModulusPolynomialRingZq};
180 use std::str::FromStr;
181
182 /// Ensures that the hamming weight is computed correctly.
183 #[test]
184 fn hamming_weight() {
185 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 8").unwrap();
186 let mat0 = MatPolyOverZ::new(3, 4);
187 let mat0 = MatPolynomialRingZq::from((&mat0, &modulus));
188 let mat1 = MatPolyOverZ::from_str("[[1 -2, 2 3 2],[2 2 0, 1 -5],[1 -2, 0]]").unwrap();
189 let mat1 = MatPolynomialRingZq::from((&mat1, &modulus));
190
191 let hw0 = mat0.hamming_weight();
192 let hw1 = mat1.hamming_weight();
193
194 assert_eq!(0, hw0);
195 assert_eq!(6, hw1);
196 }
197}