qfall_math/integer_mod_q/modulus_polynomial_ring_zq/

from.rs

// Copyright 2023 Marcel Luca Schmidt, 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 create a [`ModulusPolynomialRingZq`] value from other types.
//!
//! The explicit functions contain the documentation.

use super::ModulusPolynomialRingZq;
use crate::{
    error::MathError,
    integer::{PolyOverZ, Z},
    integer_mod_q::{Modulus, PolyOverZq},
    macros::for_others::implement_for_owned,
    traits::GetCoefficient,
};
use std::{rc::Rc, str::FromStr};

impl<Mod: Into<Modulus>> From<(&PolyOverZ, Mod)> for ModulusPolynomialRingZq {
    /// Creates a [`ModulusPolynomialRingZq`] from a [`PolyOverZ`] and a value that implements [`Into<Modulus>`].
    /// It requires that the leading coefficient is `1`.
    ///
    /// Parameters:
    /// - `poly`: the coefficients of the polynomial.
    /// - `modulus`: the modulus by which each entry is reduced.
    ///
    /// Returns a new [`ModulusPolynomialRingZq`] with the coefficients from the
    /// [`PolyOverZ`] instance under the specified [`Modulus`] value.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::{ModulusPolynomialRingZq, Modulus};
    /// use qfall_math::integer::PolyOverZ;
    /// use std::str::FromStr;
    ///
    /// let poly = PolyOverZ::from_str("4  0 1 102 1").unwrap();
    ///
    /// let mod_poly = ModulusPolynomialRingZq::from((&poly, 100));
    ///
    /// let poly_cmp = ModulusPolynomialRingZq::from_str("4  0 1 2 1 mod 100").unwrap();
    /// assert_eq!(poly_cmp, mod_poly);
    /// ```
    ///
    /// # Panics ...
    /// - if `modulus` is smaller than `2`, or
    /// - if the modulus polynomial is of degree smaller than `1`.
    /// - if the leading coefficient is not `1.`
    fn from((poly, modulus): (&PolyOverZ, Mod)) -> Self {
        let poly_zq = PolyOverZq::from((poly, modulus));

        check_poly_mod(&poly_zq).unwrap();

        Self::from(poly_zq)
    }
}

impl<Mod: Into<Modulus>> From<(PolyOverZ, Mod)> for ModulusPolynomialRingZq {
    /// Creates a [`ModulusPolynomialRingZq`] from a [`PolyOverZ`] and a value that implements [`Into<Modulus>`].
    /// It requires that the leading coefficient is `1`.
    ///
    /// Parameters:
    /// - `poly`: the coefficients of the polynomial.
    /// - `modulus`: the modulus by which each entry is reduced.
    ///
    /// Returns a new [`ModulusPolynomialRingZq`] with the coefficients from the
    /// [`PolyOverZ`] instance under the specified [`Modulus`] value.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer::PolyOverZ;
    /// use std::str::FromStr;
    ///
    /// let poly = PolyOverZ::from_str("4  0 1 102 1").unwrap();
    ///
    /// let mod_poly = ModulusPolynomialRingZq::from((poly, 100));
    ///
    /// let poly_cmp = ModulusPolynomialRingZq::from_str("4  0 1 2 1 mod 100").unwrap();
    /// assert_eq!(poly_cmp, mod_poly);
    /// ```
    ///
    /// # Panics ...
    /// - if `modulus` is smaller than `2`, or
    /// - if the modulus polynomial is of degree smaller than `1`.
    /// - if the leading coefficient is not `1.`
    fn from((poly, modulus): (PolyOverZ, Mod)) -> Self {
        let poly_zq = PolyOverZq::from((poly, modulus));

        check_poly_mod(&poly_zq).unwrap();

        Self::from(poly_zq)
    }
}

impl From<&PolyOverZq> for ModulusPolynomialRingZq {
    /// Creates a Modulus object of type [`ModulusPolynomialRingZq`]
    /// for [`PolynomialRingZq`](crate::integer_mod_q::PolynomialRingZq).
    /// It requires that the leading coefficient is `1`.
    ///
    /// Parameters:
    /// - `poly`: the polynomial which is used as the modulus.
    ///
    /// Returns a new [`ModulusPolynomialRingZq`] object with the coefficients
    /// and modulus from the [`PolyOverZq`] instance.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let poly = PolyOverZq::from_str("3  1 0 1 mod 17").unwrap();
    /// let mod_poly = ModulusPolynomialRingZq::try_from(&poly).unwrap();
    /// ```
    ///
    /// # Panics ...
    /// - if `modulus` is smaller than `2`, or
    /// - if the modulus polynomial is of degree smaller than `1`.
    /// - if the leading coefficient is not `1.`
    fn from(poly: &PolyOverZq) -> Self {
        check_poly_mod(poly).unwrap();

        let non_zero = non_zero_positions(poly);

        Self {
            modulus: Rc::new(poly.clone()),
            ntt_basis: Rc::new(None),
            non_zero,
        }
    }
}

implement_for_owned!(PolyOverZq, ModulusPolynomialRingZq, From);

impl From<&ModulusPolynomialRingZq> for ModulusPolynomialRingZq {
    // Only the smart pointer is increased here.

    /// Alias for [`ModulusPolynomialRingZq::clone`].
    fn from(value: &ModulusPolynomialRingZq) -> Self {
        value.clone()
    }
}

impl FromStr for ModulusPolynomialRingZq {
    type Err = MathError;

    /// Creates a Modulus object of type [`ModulusPolynomialRingZq`]
    /// for [`PolynomialRingZq`](crate::integer_mod_q::PolynomialRingZq). This first
    /// converts the provided string into a [`PolyOverZq`] and then into the Modulus object.
    /// It requires that the leading coefficient is `1`.
    ///
    /// **Warning**: If the input string starts with a correctly formatted
    /// [`PolyOverZ`](crate::integer::PolyOverZ) object, the rest of the string
    /// until the `"mod"` is ignored. This means that the input string
    /// `"4  0 1 2 1 mod 13"` is the same as `"4  0 1 2 1 4 5 6 7 mod 13"`.
    ///
    /// Parameters:
    /// - `s`: has to be a valid string to create a [`PolyOverZq`].
    ///   For further information see [`PolyOverZq::from_str`].
    ///
    /// Note that the `[#number of coefficients]` and `[0th coefficient]`
    /// are divided by two spaces and the string for the polynomial is trimmed,
    /// i.e. all whitespaces before around the polynomial and the modulus are ignored.
    ///
    /// Returns a [`ModulusPolynomialRingZq`] or an error if the provided string was not
    /// formatted correctly or the modulus was smaller than `2`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use std::str::FromStr;
    ///
    /// let poly_mod = ModulusPolynomialRingZq::from_str("3  1 0 1 mod 17").unwrap();
    /// ```
    /// # Errors and Failures
    /// - Returns a [`MathError`] of type
    ///   [`StringConversionError`](MathError::StringConversionError)
    ///     - if the provided first half of the string was not formatted correctly to
    ///       create a [`PolyOverZ`],
    ///     - if the provided second half of the
    ///       string was not formatted correctly to create a [`Modulus`],
    ///     - if the number of coefficients was smaller than the number provided
    ///       at the start of the provided string,
    ///     - if the provided value did not contain two whitespaces, or
    ///     - if the delimiter `mod` could not be found.
    ///     - For further information see [`PolyOverZq::from_str`].
    /// - Returns a [`MathError`] of type
    ///   [`InvalidModulus`](MathError::InvalidModulus)
    ///     - if `modulus` is smaller than `2`, or
    ///     - if the modulus polynomial is of degree smaller than `1`.
    ///     - if the leading coefficient is not `1`.
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let poly_zq = PolyOverZq::from_str(s)?;

        check_poly_mod(&poly_zq)?;

        Ok(Self::from(poly_zq))
    }
}

/// Fills a vector with the position of all non-zero coefficients in a [`PolyOverZq`] except the leading coefficient.
///
/// Parameters:
/// - `poly`: defines the polynomial whose positions of non-zero coefficients are output
///
/// Returns a [`Vec<usize>`] containing the positions of all non-zero coefficients except the leading coefficient.
///
/// # Examples
/// ```compile_fail
/// use qfall_math::integer_mod_q::PolyOverZq;
/// use std::str::FromStr;
///
/// let poly_zq = PolyOverZq::from_str("4  1 0 0 1 mod 17").unwrap();
///
/// let non_zero = non_zero_positions(&poly_zq);
/// ```
pub(crate) fn non_zero_positions(poly: &PolyOverZq) -> Vec<usize> {
    let mut non_zero = Vec::new();
    for i in 0..poly.get_degree() {
        let coeff: Z = poly.get_coeff(i).unwrap();
        if coeff != 0 {
            non_zero.push(i.try_into().unwrap());
        }
    }
    non_zero
}

/// Checks weather a given [`PolyOverZq`] can be used as a [`ModulusPolynomialRingZq`].
/// It requires that the leading coefficient is `1`.
///
/// Parameters:
/// - `poly_zq`: the [`PolyOverZq`] value that should be checked.
///
/// Returns an empty `Ok`, or an [`MathError`] if the polynomial is no valid modulus polynomial.
///
/// # Examples
/// ```compile_fail
/// use qfall_math::integer_mod_q::PolyOverZq;
/// use std::str::FromStr;
///
/// let poly_zq = PolyOverZq::from_str("2  1 1 mod 17").unwrap();
///
/// check_poly_mod(&poly_zq)?
/// ```
///
/// # Errors and Failures
/// - Returns a [`MathError`] of type
///   [`InvalidModulus`](MathError::InvalidModulus)
///   if the modulus polynomial is of degree less than `1`.
/// - Returns a [`MathError`] of type
///   [`InvalidModulus`](MathError::InvalidModulus)
///   if the leading coefficient is not `1`.
pub(crate) fn check_poly_mod(poly_zq: &PolyOverZq) -> Result<(), MathError> {
    let leading_coefficient: Z = poly_zq.get_coeff(poly_zq.get_degree())?;
    if poly_zq.get_degree() < 1 {
        return Err(MathError::InvalidModulus(poly_zq.to_string()));
    }
    if leading_coefficient != 1 {
        return Err(MathError::InvalidModulus(format!(
            ". The leading coefficient needs to be 1, but it is {leading_coefficient}"
        )));
    }

    Ok(())
}

/// Most tests with specific values are covered in [`PolyOverZq`](crate::integer_mod_q::PolyOverZq)
/// since the format is reused, we omit some tests
#[cfg(test)]
mod test_availability {
    use super::*;
    use crate::integer_mod_q::PolyOverZq;
    use std::str::FromStr;

    /// Ensure that the from function can be called with several types.
    #[test]
    fn availability() {
        let poly = PolyOverZ::from_str("2  1 1").unwrap();
        let poly_zq = PolyOverZq::from_str("4  1 0 0 1 mod 17").unwrap();

        let _ = ModulusPolynomialRingZq::from((&poly, 5));
        let _ = ModulusPolynomialRingZq::from((poly.clone(), 5));

        let _ = ModulusPolynomialRingZq::from(&poly_zq);
        let _ = ModulusPolynomialRingZq::from(poly_zq);
    }
}

/// Most tests with specific values are covered in [`PolyOverZq`](crate::integer_mod_q::PolyOverZq)
/// since the format is reused, we omit some tests
#[cfg(test)]
mod test_try_from_poly_z {
    use crate::{integer::PolyOverZ, integer_mod_q::ModulusPolynomialRingZq};
    use std::str::FromStr;

    /// Ensure that primes and non-primes work as modulus
    #[test]
    fn poly_z_primes() {
        let poly_z = PolyOverZ::from_str("2  2 1").unwrap();

        let _ = ModulusPolynomialRingZq::from((&poly_z, 10));
        let _ = ModulusPolynomialRingZq::from((poly_z, 11));
    }

    /// Ensure that the function panics if the modulus polynomial is 0
    #[test]
    #[should_panic]
    fn panic_0() {
        let poly = PolyOverZ::from(0);

        let _ = ModulusPolynomialRingZq::from((poly, 17));
    }
}

/// Most tests with specific values are covered in [`PolyOverZq`](crate::integer_mod_q::PolyOverZq)
/// since the format is reused, we omit some tests
#[cfg(test)]
mod test_try_from_integer_mod {
    use std::str::FromStr;

    use crate::{integer::PolyOverZ, integer_mod_q::ModulusPolynomialRingZq};

    /// Ensure that primes and non-primes work as modulus
    #[test]
    fn mod_primes() {
        let _ = ModulusPolynomialRingZq::from_str("3  3 0 1 mod 17").unwrap();
        let _ = ModulusPolynomialRingZq::from_str("3  3 0 1 mod 18").unwrap();
    }

    /// Ensure that the function panics if the modulus polynomial is a constant polynomial
    #[test]
    #[should_panic]
    fn panic_degree_0() {
        let poly = PolyOverZ::from_str("1 1").unwrap();
        let _ = ModulusPolynomialRingZq::from((poly, 17));
    }
}

/// Most tests with specific values are covered in [`PolyOverZq`](crate::integer_mod_q::PolyOverZq)
/// since the format is reused, we omit some tests
#[cfg(test)]
mod test_try_from_poly_zq {
    use crate::{integer_mod_q::ModulusPolynomialRingZq, integer_mod_q::PolyOverZq};
    use std::str::FromStr;

    /// Ensure that it works with large coefficients
    #[test]
    fn working_large_entries() {
        let poly_mod =
            PolyOverZq::from_str(&format!("4  0 1 {} 1 mod {}", u64::MAX, 2_i32.pow(16) + 1))
                .unwrap();
        let _ = ModulusPolynomialRingZq::from(&poly_mod);
    }

    /// Ensure that primes and non-primes work as modulus
    #[test]
    fn poly_zq_primes() {
        let poly_zq_1 = PolyOverZq::from_str("2  1 1 mod 10").unwrap();
        let poly_zq_2 = PolyOverZq::from_str("2  1 1 mod 11").unwrap();

        let _ = ModulusPolynomialRingZq::from(poly_zq_1);
        let _ = ModulusPolynomialRingZq::from(poly_zq_2);
    }

    /// Ensure that the function panics if the modulus polynomial is 0
    #[test]
    #[should_panic]
    fn panic_0() {
        let poly = PolyOverZq::from((0, 17));

        let _ = ModulusPolynomialRingZq::from(poly);
    }

    /// Ensure that the function panics if the leading coefficient is not `1`
    #[test]
    #[should_panic]
    fn panic_leading_coefficient() {
        let poly = PolyOverZq::from_str("2  1 2 mod 10").unwrap();

        let _ = ModulusPolynomialRingZq::from(poly);
    }
}

/// most tests with specific values are covered in [`PolyOverZq`](crate::integer_mod_q::PolyOverZq)
/// since the format is reused, we omit some tests
#[cfg(test)]
mod test_from_str {
    use crate::integer_mod_q::ModulusPolynomialRingZq;
    use std::str::FromStr;

    /// Ensure that at input of a wrong format an error is returned
    #[test]
    fn wrong_modulus_fmt() {
        assert!(ModulusPolynomialRingZq::from_str("3  4 0 1 mod -17").is_err());
        assert!(ModulusPolynomialRingZq::from_str("3  4 0 1 mod 17 mod 42").is_err());
        assert!(ModulusPolynomialRingZq::from_str("3  4 0 1 mod 0").is_err());
        assert!(ModulusPolynomialRingZq::from_str("3  4 0 1 mod 1 7").is_err());
        assert!(ModulusPolynomialRingZq::from_str("3  4 0 1 mod ba").is_err());
    }

    /// Ensure that large coefficients work
    #[test]
    fn working_large_entries() {
        assert!(
            ModulusPolynomialRingZq::from_str(&format!(
                "4  0 1 {} 1 mod {}",
                u64::MAX,
                2_i32.pow(16) + 1
            ))
            .is_ok()
        );
    }

    /// Ensure that primes and non-primes work as modulus
    #[test]
    fn poly_zq_primes() {
        assert!(ModulusPolynomialRingZq::from_str("4  0 1 3 1 mod 10").is_ok());
        assert!(ModulusPolynomialRingZq::from_str("4  0 1 3 1 mod 11").is_ok());
    }
}