qfall_math/integer_mod_q/poly_over_zq/
properties.rs

1// Copyright 2023 Marvin Beckmann
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//! Implementations to check certain properties of [`PolyOverZq`].
10//! This includes checks such as reducibility.
11
12use super::PolyOverZq;
13use flint3_sys::{
14    fmpz_mod_poly_is_irreducible, {fmpz_mod_poly_degree, fmpz_mod_poly_is_one},
15};
16
17impl PolyOverZq {
18    /// Checks if a [`PolyOverZq`] is irreducible.
19    ///
20    /// Returns `true` if the polynomial is irreducible and `false` otherwise.
21    ///
22    /// # Examples
23    /// ```
24    /// use qfall_math::integer_mod_q::PolyOverZq;
25    /// use std::str::FromStr;
26    ///
27    /// let poly_irr = PolyOverZq::from_str("2  1 1 mod 17").unwrap();
28    /// // returns true, since X + 1 is irreducible
29    /// assert!(poly_irr.is_irreducible());
30    /// ```
31    pub fn is_irreducible(&self) -> bool {
32        // prevent running into FLINT error
33        if !self.get_mod().is_prime() {
34            return false;
35        }
36
37        1 == unsafe {
38            fmpz_mod_poly_is_irreducible(&self.poly, self.modulus.get_fmpz_mod_ctx_struct())
39        }
40    }
41
42    /// Checks if a [`PolyOverZq`] is the constant polynomial with coefficient `1`.
43    ///
44    /// Returns `true` if there is only one coefficient, which is `1`.
45    ///
46    /// # Examples
47    /// ```
48    /// use qfall_math::integer_mod_q::PolyOverZq;
49    /// use std::str::FromStr;
50    ///
51    /// let value = PolyOverZq::from_str("1  1 mod 4").unwrap();
52    /// assert!(value.is_one());
53    /// ```
54    pub fn is_one(&self) -> bool {
55        1 == unsafe { fmpz_mod_poly_is_one(&self.poly, self.modulus.get_fmpz_mod_ctx_struct()) }
56    }
57
58    /// Checks if every entry of a [`PolyOverZq`] is `0`.
59    ///
60    /// Returns `true` if [`PolyOverZq`] has no coefficients.
61    ///
62    /// # Examples
63    /// ```
64    /// use qfall_math::integer_mod_q::PolyOverZq;
65    /// use std::str::FromStr;
66    ///
67    /// let value = PolyOverZq::from_str("0 mod 7").unwrap();
68    /// assert!(value.is_zero());
69    /// ```
70    pub fn is_zero(&self) -> bool {
71        -1 == unsafe { fmpz_mod_poly_degree(&self.poly, self.modulus.get_fmpz_mod_ctx_struct()) }
72    }
73}
74
75#[cfg(test)]
76mod test_is_irreducible {
77    use crate::integer_mod_q::PolyOverZq;
78    use std::str::FromStr;
79
80    /// Ensure that a irreducible [`PolyOverZq`] returns `true`.
81    #[test]
82    fn poly_is_irreducible() {
83        // 9X^2 + 12X + 10 is irreducible over 17
84        let poly_irr = PolyOverZq::from_str("3  10 12 9 mod 17").unwrap();
85        assert!(poly_irr.is_irreducible());
86    }
87
88    /// Ensure that a reducible [`PolyOverZq`] returns `false`.
89    #[test]
90    fn poly_is_reducible() {
91        let poly_irr = PolyOverZq::from_str("3  1 2 1 mod 17").unwrap();
92        assert!(!poly_irr.is_irreducible());
93    }
94}
95
96#[cfg(test)]
97mod test_is_one {
98    use super::PolyOverZq;
99    use std::str::FromStr;
100
101    /// Ensure that is_one returns `true` for the one polynomial.
102    #[test]
103    fn one_detection() {
104        let one = PolyOverZq::from_str("1  1 mod 7").unwrap();
105        let one_2 = PolyOverZq::from_str("2  1 14 mod 7").unwrap();
106
107        assert!(one.is_one());
108        assert!(one_2.is_one());
109    }
110
111    /// Ensure that is_one returns `false` for other polynomials.
112    #[test]
113    fn one_rejection() {
114        let small = PolyOverZq::from_str("4  1 0 0 1 mod 7").unwrap();
115        let large =
116            PolyOverZq::from_str(&format!("1  {} mod {}", (u128::MAX - 1) / 2 + 2, u128::MAX)) // 2^127 + 1 the last memory entry is `1`
117                .unwrap();
118
119        assert!(!small.is_one());
120        assert!(!large.is_one());
121    }
122}
123
124#[cfg(test)]
125mod test_is_zero {
126    use super::PolyOverZq;
127    use std::str::FromStr;
128
129    /// Ensure that is_zero returns `true` for the zero polynomial.
130    #[test]
131    fn zero_detection() {
132        let zero = PolyOverZq::from_str("0 mod 7").unwrap();
133        let zero_2 = PolyOverZq::from_str("2  7 14 mod 7").unwrap();
134
135        assert!(zero.is_zero());
136        assert!(zero_2.is_zero());
137    }
138
139    /// Ensure that is_zero returns `false` for non-zero polynomials.
140    #[test]
141    fn zero_rejection() {
142        let small = PolyOverZq::from_str("4  0 0 0 1 mod 7").unwrap();
143        let large =
144            PolyOverZq::from_str(&format!("1  {} mod {}", (u128::MAX - 1) / 2 + 1, u128::MAX)) // last 126 bits are 0
145                .unwrap();
146
147        assert!(!small.is_zero());
148        assert!(!large.is_zero());
149    }
150}
qfall_math/integer_mod_q/poly_over_zq/properties.rs

qfall_math/integer_mod_q/poly_over_zq/
properties.rs
