qfall_math/integer_mod_q/poly_over_zq/

get.rs

// Copyright 2023 Marvin Beckmann
//
// This file is part of qFALL-math.
//
// qFALL-math is free software: you can redistribute it and/or modify it under
// the terms of the Mozilla Public License Version 2.0 as published by the
// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.

//! Implementations to get information about a [`PolyOverZq`] polynomial.

use super::PolyOverZq;
use crate::{
    integer::{PolyOverZ, Z},
    integer_mod_q::{Modulus, Zq},
    traits::{GetCoefficient, SetCoefficient},
};
use flint3_sys::{fmpz_mod_poly_degree, fmpz_mod_poly_get_coeff_fmpz, fmpz_mod_poly_get_fmpz_poly};

impl GetCoefficient<Zq> for PolyOverZq {
    /// Returns the coefficient of a polynomial [`PolyOverZq`] as a [`Zq`].
    ///
    /// If an index is provided which exceeds the highest set coefficient, `0` is returned.
    ///
    /// Parameters:
    /// - `index`: the index of the coefficient to get (has to be positive)
    ///
    /// Returns the coefficient as a [`Zq`], or a [`MathError`](crate::error::MathError) if the provided index
    /// is negative and therefore invalid, or it does not fit into an [`i64`].
    ///
    /// # Examples
    /// ```
    /// use qfall_math::traits::*;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use qfall_math::integer_mod_q::Zq;
    /// use std::str::FromStr;
    ///
    /// let poly = PolyOverZq::from_str("4  0 1 2 3 mod 17").unwrap();
    ///
    /// let coeff_0: Zq = poly.get_coeff(0).unwrap();
    /// let coeff_1: Zq = unsafe{ poly.get_coeff_unchecked(1) };
    /// let coeff_4: Zq = poly.get_coeff(4).unwrap();
    ///
    /// assert_eq!(Zq::from((0, 17)), coeff_0);
    /// assert_eq!(Zq::from((1, 17)), coeff_1);
    /// assert_eq!(Zq::from((0, 17)), coeff_4);
    /// ```
    ///
    /// # Safety
    /// To use this function safely, make sure that the selected index
    /// is greater or equal than `0`.
    unsafe fn get_coeff_unchecked(&self, index: i64) -> Zq {
        let out_z: Z = unsafe { self.get_coeff_unchecked(index) };
        Zq::from((out_z, &self.modulus))
    }
}

impl GetCoefficient<Z> for PolyOverZq {
    /// Returns the coefficient of a polynomial [`PolyOverZq`] as a [`Z`].
    ///
    /// If an index is provided which exceeds the highest set coefficient, `0` is returned.
    ///
    /// Parameters:
    /// - `index`: the index of the coefficient to get (has to be positive)
    ///
    /// Returns the coefficient as a [`Z`], or a [`MathError`](crate::error::MathError) if the provided index
    /// is negative and therefore invalid, or it does not fit into an [`i64`].
    ///
    /// # Examples
    /// ```
    /// use qfall_math::traits::*;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use qfall_math::integer::Z;
    /// use std::str::FromStr;
    ///
    /// let poly = PolyOverZq::from_str("4  0 1 2 3 mod 17").unwrap();
    ///
    /// let coeff_0: Z = poly.get_coeff(0).unwrap();
    /// let coeff_1: Z = unsafe{ poly.get_coeff_unchecked(1) };
    /// let coeff_4: Z = poly.get_coeff(4).unwrap();
    ///
    /// assert_eq!(Z::ZERO, coeff_0);
    /// assert_eq!(Z::ONE, coeff_1);
    /// assert_eq!(Z::ZERO, coeff_4);
    /// ```
    ///
    /// # Safety
    /// To use this function safely, make sure that the selected index
    /// is greater or equal than `0`.
    unsafe fn get_coeff_unchecked(&self, index: i64) -> Z {
        let mut out = Z::default();
        unsafe {
            fmpz_mod_poly_get_coeff_fmpz(
                &mut out.value,
                &self.poly,
                index,
                self.modulus.get_fmpz_mod_ctx_struct(),
            )
        }
        out
    }
}

impl PolyOverZq {
    /// Returns the degree of a polynomial [`PolyOverZq`] as a [`i64`].
    /// The zero polynomial has degree `-1`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let poly = PolyOverZq::from_str("4  0 1 2 3 mod 7").unwrap();
    ///
    /// let degree = poly.get_degree(); // This would only return 3
    /// ```
    pub fn get_degree(&self) -> i64 {
        unsafe { fmpz_mod_poly_degree(&self.poly, self.modulus.get_fmpz_mod_ctx_struct()) }
    }

    /// Returns the modulus of the polynomial as a [`Modulus`].
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let matrix = PolyOverZq::from_str("2  1 3 mod 7").unwrap();
    /// let modulus = matrix.get_mod();
    /// ```
    pub fn get_mod(&self) -> Modulus {
        self.modulus.clone()
    }

    /// Returns a representative polynomial of the [`PolyOverZq`] element with coefficients centered around `0`.
    ///
    /// The output [`PolyOverZ`] has coefficients in the range `(-⌈modulus/2⌉, ⌊modulus/2⌋]`,
    /// i.e. `[-(modulus-1)/2, (modulus-1)/2]` for odd moduli and `(-modulus/2, modulus/2]` for even moduli.
    /// Hence, the positive representative is chosen for the element `modulus/2` of even moduli.
    /// Use [`PolyOverZq::get_representative_least_nonnegative_residue`] if they should be
    /// in the range `[0, modulus)`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use qfall_math::integer::PolyOverZ;
    /// use std::str::FromStr;
    ///
    /// let value = PolyOverZq::from_str("2  10 11 mod 21").unwrap();
    ///
    /// let least_abs_residue = value.get_representative_least_absolute_residue();
    ///
    /// assert_eq!(PolyOverZ::from_str("2  10 -10").unwrap(), least_abs_residue);
    /// ```
    pub fn get_representative_least_absolute_residue(&self) -> PolyOverZ {
        let mut out = PolyOverZ::default();
        for i in 0..=self.get_degree() {
            let coeff: Zq = unsafe { self.get_coeff_unchecked(i) };
            let lar_coeff = coeff.get_representative_least_absolute_residue();
            unsafe { out.set_coeff_unchecked(i, lar_coeff) };
        }
        out
    }

    /// Returns a representative polynomial of the [`PolyOverZq`] element.
    ///
    /// The representation of the coefficients is in the range `[0, modulus)`.
    /// Use [`PolyOverZq::get_representative_least_absolute_residue`] if they should be
    /// in the range `(-⌈modulus/2⌉, ⌊modulus/2⌋]`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer::PolyOverZ;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let poly_zq = PolyOverZq::from_str("4  -3 0 31 1 mod 17").unwrap();
    ///
    /// let poly_z = poly_zq.get_representative_least_nonnegative_residue();
    ///
    /// let cmp_poly = PolyOverZ::from_str("4  14 0 14 1").unwrap();
    /// assert_eq!(cmp_poly, poly_z);
    /// ```
    pub fn get_representative_least_nonnegative_residue(&self) -> PolyOverZ {
        let mut out = PolyOverZ::default();
        unsafe {
            fmpz_mod_poly_get_fmpz_poly(
                &mut out.poly,
                &self.poly,
                self.modulus.get_fmpz_mod_ctx_struct(),
            )
        };
        out
    }
}

// We omit the tests for the value of the [`Zq`], and focus on the [`Modulus`] being set correctly
// since get_coefficient for [`Z`] is called, where we will check the value itself.
#[cfg(test)]
mod test_get_coeff_zq_modulus {
    use crate::{
        integer_mod_q::{Modulus, PolyOverZq, Zq},
        traits::GetCoefficient,
    };
    use std::str::FromStr;

    /// Ensure that the [`Modulus`] is transferred correctly when accessing an index out of bounds.
    #[test]
    fn index_out_of_range_modulus() {
        let modulus_str = format!("17{}", u64::MAX);
        let modulus = Modulus::from_str(&modulus_str).unwrap();

        let poly = PolyOverZq::from_str(&format!("4  0 1 2 3 mod {modulus_str}")).unwrap();

        let zero_coeff: Zq = poly.get_coeff(4).unwrap();

        assert_eq!(modulus, zero_coeff.modulus);
    }

    /// Ensure that the [`Modulus`] is transferred correctly when accessing an index in bounds.
    #[test]
    fn index_in_range_modulus() {
        let modulus_str = format!("17{}", u64::MAX);
        let modulus = Modulus::from_str(&modulus_str).unwrap();

        let poly = PolyOverZq::from_str(&format!("4  0 1 2 3 mod {modulus_str}")).unwrap();

        let third_coeff: Zq = poly.get_coeff(3).unwrap();

        assert_eq!(modulus, third_coeff.modulus);
    }
}

#[cfg(test)]
mod test_get_coeff_z {
    use crate::{integer::Z, integer_mod_q::PolyOverZq, traits::GetCoefficient};
    use std::str::FromStr;

    /// Ensure that `0` is returned if the provided index is not yet set.
    #[test]
    fn index_out_of_range() {
        let modulus_str = format!("17{}", u64::MAX);

        let poly = PolyOverZq::from_str(&format!("4  0 1 2 3 mod {modulus_str}")).unwrap();

        let zero_coeff: Z = poly.get_coeff(4).unwrap();

        assert_eq!(0, zero_coeff);
    }

    /// Tests if positive coefficients are returned correctly.
    #[test]
    fn positive_coeff() {
        let modulus_str = format!("17{}", u64::MAX);

        let poly = PolyOverZq::from_str(&format!("4  0 1 2 3 mod {modulus_str}")).unwrap();

        let coeff: Z = poly.get_coeff(2).unwrap();

        assert_eq!(2, coeff);
    }

    /// Tests if large coefficients are returned correctly.
    #[test]
    fn large_coeff() {
        let modulus_str = format!("17{}", u64::MAX);
        let large_string = format!("2  {} {} mod {modulus_str}", u64::MAX, i64::MAX);
        let poly = PolyOverZq::from_str(&large_string).unwrap();

        let coefficint_1: Z = poly.get_coeff(0).unwrap();
        let coefficint_2: Z = poly.get_coeff(1).unwrap();

        assert_eq!(u64::MAX, coefficint_1);
        assert_eq!(i64::MAX, coefficint_2);
    }

    /// Tests if large negative coefficients are returned correctly.
    #[test]
    fn large_modulus_applied_negative_large_coefficient() {
        let modulus_str = format!("{}", u64::MAX);
        let large_string = format!("2  -{} {} mod {modulus_str}", u64::MAX, i64::MAX);
        let poly = PolyOverZq::from_str(&large_string).unwrap();

        let coefficint_1: Z = poly.get_coeff(0).unwrap();
        let coefficint_2: Z = poly.get_coeff(1).unwrap();

        assert_eq!(0, coefficint_1);
        assert_eq!(i64::MAX, coefficint_2);
    }
}

#[cfg(test)]
mod test_get_degree {
    use crate::integer_mod_q::PolyOverZq;
    use std::str::FromStr;

    /// Ensure that degree is working.
    #[test]
    fn degree() {
        let poly = PolyOverZq::from_str("4  0 1 2 3 mod 7").unwrap();

        let deg = poly.get_degree();

        assert_eq!(3, deg);
    }

    /// Ensure that degree is working for constant polynomials.
    #[test]
    fn degree_constant() {
        let poly_1 = PolyOverZq::from_str("1  1 mod 19").unwrap();
        let poly_2 = PolyOverZq::from_str("0 mod 19").unwrap();

        let deg_1 = poly_1.get_degree();
        let deg_2 = poly_2.get_degree();

        assert_eq!(0, deg_1);
        assert_eq!(-1, deg_2);
    }

    /// Ensure that degree is working for polynomials with leading 0 coefficients.
    #[test]
    fn degree_leading_zeros() {
        let poly = PolyOverZq::from_str("4  1 0 0 0 mod 199").unwrap();

        let deg = poly.get_degree();

        assert_eq!(0, deg);
    }

    /// Ensure that degree is working for polynomials with many coefficients
    /// flint does not reduce the exponent due to computational cost.
    #[test]
    fn degree_many_coefficients() {
        let poly_1 = PolyOverZq::from_str("7  1 2 3 4 8 1 3 mod 2").unwrap();
        let poly_2 = PolyOverZq::from_str(&format!(
            "7  1 2 3 4 8 {} {} mod {}",
            u64::MAX,
            i64::MAX,
            u128::MAX
        ))
        .unwrap();

        let deg_1 = poly_1.get_degree();
        let deg_2 = poly_2.get_degree();

        assert_eq!(6, deg_1);
        assert_eq!(6, deg_2);
    }
}

#[cfg(test)]
mod test_mod {
    use crate::integer_mod_q::{Modulus, PolyOverZq};
    use std::str::FromStr;

    /// Ensure that the getter for modulus works correctly.
    #[test]
    fn get_mod() {
        let poly = PolyOverZq::from_str("2  1 2 mod 7").unwrap();

        assert_eq!(poly.get_mod(), Modulus::from(7));
    }

    /// Ensure that the getter for modulus works with large numbers.
    #[test]
    fn get_mod_large() {
        let poly = PolyOverZq::from_str(&format!("2  1 2 mod {}", u64::MAX)).unwrap();

        assert_eq!(poly.get_mod(), Modulus::from(u64::MAX));
    }
}

#[cfg(test)]
mod test_get_representative_least_absolute_residue {
    use crate::{integer::PolyOverZ, integer_mod_q::PolyOverZq};
    use std::str::FromStr;

    /// Check whether `get_representative_least_absolute_residue` outputs the correct value for large values
    #[test]
    fn large_numbers() {
        let poly_zq = PolyOverZq::from_str(&format!(
            "2  {} {} mod {}",
            i64::MAX,
            u64::MAX - 1,
            u64::MAX
        ))
        .unwrap();

        let poly_z = poly_zq.get_representative_least_absolute_residue();

        let cmp_poly = PolyOverZ::from_str(&format!("2  {} -1", i64::MAX)).unwrap();
        assert_eq!(cmp_poly, poly_z);
    }

    /// Check whether `get_representative_least_absolute_residue` outputs the correct value for special cases
    #[test]
    fn special_numbers() {
        let poly_zq = PolyOverZq::from_str("3  10 0 11 mod 21").unwrap();

        let poly_z = poly_zq.get_representative_least_absolute_residue();

        let cmp_poly = PolyOverZ::from_str("3  10 0 -10").unwrap();
        assert_eq!(cmp_poly, poly_z);
    }

    /// Returns the coefficients `0, 1, ..., modulus - 1` and their representatives
    /// according to `mod±` as defined in FIPS 204 as strings.
    fn coefficients_and_representatives(modulus: i64) -> (String, String) {
        let coefficients: Vec<String> = (0..modulus).map(|value| value.to_string()).collect();
        let representatives: Vec<String> = (0..modulus)
            .map(|value| {
                if value > modulus / 2 {
                    value - modulus
                } else {
                    value
                }
                .to_string()
            })
            .collect();
        (coefficients.join(" "), representatives.join(" "))
    }

    /// Checks whether every coefficient is mapped into `(-⌈modulus/2⌉, ⌊modulus/2⌋]`
    /// for an odd and an even modulus, i.e. `modulus/2` is mapped to the positive representative.
    #[test]
    fn full_range() {
        for modulus in [10, 11] {
            let (coefficients, representatives) = coefficients_and_representatives(modulus);
            let poly_zq =
                PolyOverZq::from_str(&format!("{modulus}  {coefficients} mod {modulus}")).unwrap();

            let poly_z = poly_zq.get_representative_least_absolute_residue();

            let cmp_poly = PolyOverZ::from_str(&format!("{modulus}  {representatives}")).unwrap();
            assert_eq!(cmp_poly, poly_z);
        }
    }
}

#[cfg(test)]
mod test_get_representative_least_nonnegative_residue {
    use crate::{integer::PolyOverZ, integer_mod_q::PolyOverZq};
    use std::str::FromStr;

    /// Ensure that the getter works for large entries.
    #[test]
    fn large_positive() {
        let large_prime = u64::MAX - 58;
        let poly_zq = PolyOverZq::from_str(&format!("4  -1 0 0 1 mod {large_prime}")).unwrap();

        let poly_z = poly_zq.get_representative_least_nonnegative_residue();

        let cmp_poly = PolyOverZ::from_str(&format!("4  {} 0 0 1", u64::MAX - 59)).unwrap();
        assert_eq!(cmp_poly, poly_z);
    }
}