qfall_math/integer_mod_q/poly_over_zq/
norm.rs

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

qfall_math/integer_mod_q/poly_over_zq/
norm.rs
