qfall-math 0.1.1

// 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 [`PolynomialRingZq`] value from other types.
//!
//! The explicit functions contain the documentation.

use super::PolynomialRingZq;
use crate::{
    error::{MathError, StringConversionError},
    integer::PolyOverZ,
    integer_mod_q::{ModulusPolynomialRingZq, NTTPolynomialRingZq, PolyOverZq},
    macros::for_others::implement_for_owned,
};
use std::str::FromStr;

impl From<NTTPolynomialRingZq> for PolynomialRingZq {
    /// Creates a polynomial from [`NTTPolynomialRingZq`] generated with respect to the
    /// [`NTTBasisPolynomialRingZq`](crate::integer_mod_q::NTTBasisPolynomialRingZq) as part of
    /// [`ModulusPolynomialRingZq`].
    ///
    /// Parameters:
    /// - `ntt`: the NTT representation of the polynomial.
    /// - `modulus`: the modulus that is applied to the polynomial ring element.
    ///
    /// Returns a new [`PolynomialRingZq`] with the specified [`ModulusPolynomialRingZq`] and
    /// values as defined in `ntt`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::{PolynomialRingZq, PolyOverZq, ModulusPolynomialRingZq, NTTPolynomialRingZq};
    /// use qfall_math::traits::SetCoefficient;
    ///
    /// let n = 4;
    /// let modulus = 7681;
    ///
    /// let mut mod_poly = PolyOverZq::from(modulus);
    /// mod_poly.set_coeff(0, 1).unwrap();
    /// mod_poly.set_coeff(n, 1).unwrap();
    ///
    /// let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
    /// polynomial_modulus.set_ntt_unchecked(1925);
    ///
    /// let ntt = NTTPolynomialRingZq::sample_uniform(&polynomial_modulus);
    ///
    /// let res = PolynomialRingZq::from(ntt);
    /// ```
    ///
    /// # Panics ...
    /// - if the [`NTTBasisPolynomialRingZq`](crate::integer_mod_q::NTTBasisPolynomialRingZq) in `modulus`
    ///   is not set.
    fn from(ntt: NTTPolynomialRingZq) -> Self {
        ntt.inv_ntt()
    }
}

impl From<&ModulusPolynomialRingZq> for PolynomialRingZq {
    /// Creates a zero polynomial with a given [`ModulusPolynomialRingZq`].
    ///
    /// Parameters:
    /// - `modulus`: the modulus that is applied to the polynomial ring element.
    ///
    /// Returns a new constant [`PolynomialRingZq`] with the specified [`ModulusPolynomialRingZq`].
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolynomialRingZq;
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
    /// let poly = PolyOverZq::from_str("4  -1 0 1 1 mod 17").unwrap();
    /// let poly_ring = PolynomialRingZq::from((poly, &modulus));
    /// ```
    ///
    /// # Panics ...
    /// - if the moduli mismatch.
    fn from(modulus: &ModulusPolynomialRingZq) -> Self {
        let modulus = modulus.into();

        Self {
            poly: PolyOverZ::default(),
            modulus,
        }
    }
}

implement_for_owned!(ModulusPolynomialRingZq, PolynomialRingZq, From);

impl<Poly: Into<PolyOverZ>, Mod: Into<ModulusPolynomialRingZq>> From<(Poly, Mod)>
    for PolynomialRingZq
{
    /// Creates a new polynomial ring element of type [`PolynomialRingZq`].
    ///
    /// Parameters:
    /// - `poly`: the coefficients of the polynomial.
    /// - `modulus`: the modulus that is applied to the polynomial ring element.
    ///
    /// Returns a new element inside the polynomial ring.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolynomialRingZq;
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer::PolyOverZ;
    /// use std::str::FromStr;
    ///
    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
    /// let poly = PolyOverZ::from_str("4  -1 0 1 1").unwrap();
    /// let poly_ring = PolynomialRingZq::from((&poly, &modulus));
    /// ```
    fn from((poly, modulus): (Poly, Mod)) -> Self {
        let mut out = Self {
            poly: poly.into(),
            modulus: modulus.into(),
        };
        out.reduce();
        out
    }
}

impl<Mod: Into<ModulusPolynomialRingZq>> From<(&PolyOverZq, Mod)> for PolynomialRingZq {
    /// Creates a new polynomial ring element of type [`PolynomialRingZq`].
    ///
    /// Parameters:
    /// - `poly`: the coefficients of the polynomial.
    /// - `modulus`: the modulus that is applied to the polynomial ring element.
    ///
    /// Returns a new element inside the polynomial ring, if the moduli of the
    /// polynomial and the modulus match.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolynomialRingZq;
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
    /// let poly = PolyOverZq::from_str("4  -1 0 1 1 mod 17").unwrap();
    /// let poly_ring = PolynomialRingZq::from((&poly, &modulus));
    /// ```
    ///
    /// # Panics ...
    /// - if the moduli mismatch.
    fn from((poly, modulus): (&PolyOverZq, Mod)) -> Self {
        let modulus = modulus.into();

        assert_eq!(
            poly.modulus,
            modulus.get_q(),
            "The moduli of the polynomial and the modulus mismatch."
        );

        let mut out = Self {
            poly: poly.get_representative_least_nonnegative_residue(),
            modulus,
        };
        out.reduce();
        out
    }
}

impl<Mod: Into<ModulusPolynomialRingZq>> From<(PolyOverZq, Mod)> for PolynomialRingZq {
    /// Creates a new polynomial ring element of type [`PolynomialRingZq`].
    ///
    /// Parameters:
    /// - `poly`: the coefficients of the polynomial.
    /// - `modulus`: the modulus that is applied to the polynomial ring element.
    ///
    /// Returns a new element inside the polynomial ring, if the moduli of the
    /// polynomial and the modulus match.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolynomialRingZq;
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer_mod_q::PolyOverZq;
    /// use std::str::FromStr;
    ///
    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
    /// let poly = PolyOverZq::from_str("4  -1 0 1 1 mod 17").unwrap();
    /// let poly_ring = PolynomialRingZq::from((poly, &modulus));
    /// ```
    ///
    /// # Panics ...
    /// - if the moduli mismatch.
    fn from((poly, modulus): (PolyOverZq, Mod)) -> Self {
        let modulus = modulus.into();

        assert_eq!(
            poly.modulus,
            modulus.get_q(),
            "The moduli of the polynomial and the modulus mismatch."
        );

        let mut out = Self {
            poly: poly.get_representative_least_nonnegative_residue(),
            modulus,
        };
        out.reduce();
        out
    }
}

impl FromStr for PolynomialRingZq {
    type Err = MathError;

    /// Creates a polynomial ring element of type [`PolynomialRingZq`].
    ///
    /// **Warning**: If the polynomials start with a correctly formatted
    /// [`PolyOverZ`] object, the rest of the string
    /// until the `"/"` (for the first polynomial)  or `"mod"` (for the second polynomial)
    /// is ignored. This means that the input string `"4  0 1 2 3 / 2  1 1 mod 13"`
    /// is the same as `"4  0 1 2 3 4 5 6 7 / 2  1 1 mod 13"`.
    ///
    /// Parameters:
    /// - `s`: the polynomial ring element of form:
    ///   `"[#number of coefficients of element]⌴⌴[0th coefficient]⌴
    ///     [1st coefficient]⌴...⌴/⌴[#number of coefficients of polynomial modulus]⌴⌴
    ///     [0th coefficient]⌴[1st coefficient]⌴...⌴mod⌴[q]"`.
    ///
    /// Note that the `[#number of coefficients]` and `[0th coefficient]`
    /// are divided by two spaces and the strings for the polynomials are trimmed,
    /// i.e. all whitespaces around the polynomials and the modulus are ignored.
    ///
    /// Returns a [`PolynomialRingZq`] or an error if the provided string was not
    /// formatted correctly, the numbers of coefficients were smaller than the numbers
    /// provided at the start of the provided string, or the modulus was smaller than `2`.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer_mod_q::PolynomialRingZq;
    /// use std::str::FromStr;
    ///
    /// let poly = PolynomialRingZq::from_str("4  -1 0 1 1 / 4  0 1 -2 1 mod 42").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 [`ModulusPolynomialRingZq`],
    ///     - if the numbers of coefficients were smaller than the numbers provided
    ///       at the start of the provided string,
    ///     - if the provided values did not contain two whitespaces, or
    ///     - if the delimiter `/` and `mod` could not be found.
    /// - Returns a [`MathError`] of type
    ///   [`InvalidModulus`](MathError::InvalidModulus)
    ///   if the integer modulus `q` is smaller than `2`.
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let (poly_s, modulus) = match s.split_once("/") {
            Some((poly_s, modulus)) => (poly_s, modulus),
            None => {
                return Err(StringConversionError::InvalidStringToPolyRingZqInput(
                    s.to_owned(),
                ))?;
            }
        };

        let poly_over_z = PolyOverZ::from_str(poly_s)?;
        let modulus = ModulusPolynomialRingZq::from_str(modulus)?;

        Ok(Self::from((&poly_over_z, &modulus)))
    }
}

#[cfg(test)]
mod test_from_ntt_modulus_polynomial_ring_zq {
    use crate::{
        integer::{PolyOverZ, Z},
        integer_mod_q::{ModulusPolynomialRingZq, NTTPolynomialRingZq, PolynomialRingZq},
    };
    use std::str::FromStr;

    /// Ensures that `inv_ntt` works properly and that we can make a round trip and get to the same ntt representation.
    #[test]
    fn round_trip() {
        let mut mod_poly = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 257").unwrap();
        mod_poly.set_ntt_unchecked(64);

        let poly = PolyOverZ::from_str("4  103 182 146 116").unwrap();
        let poly_ring_zq = PolynomialRingZq::from((poly, &mod_poly));
        let cmp_ntt = NTTPolynomialRingZq {
            poly: vec![Z::from(113), Z::from(54), Z::from(47), Z::from(198)],
            modulus: mod_poly.clone(),
        };

        let ntt = NTTPolynomialRingZq::from(&poly_ring_zq);

        assert_eq!(ntt, cmp_ntt);

        let res_poly_ring_zq = PolynomialRingZq::from(ntt);

        assert_eq!(res_poly_ring_zq, poly_ring_zq);
    }
}

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

    /// Ensure that the default value is set correctly and that the modulus is correct
    #[test]
    fn is_reduced_large() {
        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();

        let poly_ring = PolynomialRingZq::from(&modulus);

        assert_eq!(PolyOverZ::default(), poly_ring.poly);
        assert_eq!(modulus, poly_ring.modulus);
    }

    /// Ensures that the function is still available for all values implementing
    /// `Into<ModulusPolynomialRingZq>`.
    #[test]
    fn availability() {
        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();

        let _ = PolynomialRingZq::from(&modulus);
        let _ = PolynomialRingZq::from(modulus);
    }
}

#[cfg(test)]
mod test_from_poly_over_z_modulus_polynomial_ring_zq {
    use crate::{
        integer::{PolyOverZ, Z},
        integer_mod_q::{Modulus, ModulusPolynomialRingZq, PolyOverZq, PolynomialRingZq},
    };
    use std::str::FromStr;

    const LARGE_PRIME: u64 = u64::MAX - 58;

    /// Ensure that the modulus is applied with a large prime and large coefficients
    #[test]
    fn is_reduced_large() {
        let modulus =
            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {LARGE_PRIME}")).unwrap();

        let poly =
            PolyOverZ::from_str(&format!("4  {} {} 1 1", LARGE_PRIME + 2, u64::MAX)).unwrap();
        let poly_ring = PolynomialRingZq::from((&poly, &modulus));

        let cmp_poly = PolyOverZ::from_str("3  1 58 1").unwrap();
        let cmp_poly_ring = PolynomialRingZq::from((&cmp_poly, &modulus));

        assert_eq!(poly_ring, cmp_poly_ring);
    }

    /// Ensure that two ring elements that are instantiated the same way are equal
    #[test]
    fn same_instantiation() {
        let modulus =
            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {LARGE_PRIME}")).unwrap();
        let poly =
            PolyOverZ::from_str(&format!("4  {} {} 1 1", LARGE_PRIME + 2, u64::MAX)).unwrap();

        let poly_ring_1 = PolynomialRingZq::from((&poly, &modulus));
        let poly_ring_2 = PolynomialRingZq::from((&poly, &modulus));

        assert_eq!(poly_ring_1, poly_ring_2);
    }

    /// Ensures that the function is still available for all values implementing
    /// `Into<ModulusPolynomialRingZq>`.
    #[test]
    fn availability() {
        let z = Z::from(2);
        let q = Modulus::from(17);
        let poly = PolyOverZ::from(2);
        let poly_mod = PolyOverZq::from_str("2  1 1 mod 17").unwrap();
        let modulus = ModulusPolynomialRingZq::from(&poly_mod);

        let _ = PolynomialRingZq::from((&poly, &poly_mod));
        let _ = PolynomialRingZq::from((&poly, poly_mod.clone()));
        let _ = PolynomialRingZq::from((poly.clone(), &poly_mod));
        let _ = PolynomialRingZq::from((poly.clone(), poly_mod));

        let _ = PolynomialRingZq::from((0_i8, &modulus));
        let _ = PolynomialRingZq::from((0_i16, &modulus));
        let _ = PolynomialRingZq::from((0_i32, &modulus));
        let _ = PolynomialRingZq::from((0_i64, &modulus));
        let _ = PolynomialRingZq::from((0_u8, &modulus));
        let _ = PolynomialRingZq::from((0_u16, &modulus));
        let _ = PolynomialRingZq::from((0_u32, &modulus));
        let _ = PolynomialRingZq::from((0_u64, &modulus));
        let _ = PolynomialRingZq::from((&z, &modulus));
        let _ = PolynomialRingZq::from((z, &modulus));
        let _ = PolynomialRingZq::from((&q, &modulus));
        let _ = PolynomialRingZq::from((q, &modulus));

        let _ = PolynomialRingZq::from((poly.clone(), &modulus));
        let _ = PolynomialRingZq::from((poly, modulus));
    }
}

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

    const LARGE_PRIME: u64 = u64::MAX - 58;

    /// Ensure that the modulus is applied with a large prime and large coefficients
    #[test]
    fn is_reduced_large() {
        let modulus =
            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {LARGE_PRIME}")).unwrap();

        let poly = PolyOverZq::from_str(&format!(
            "4  {} {} 1 1 mod {}",
            LARGE_PRIME + 2,
            u64::MAX,
            LARGE_PRIME
        ))
        .unwrap();
        let poly_ring = PolynomialRingZq::from((&poly, &modulus));

        let cmp_poly = PolyOverZ::from_str("3  1 58 1").unwrap();
        let cmp_poly_ring = PolynomialRingZq::from((&cmp_poly, &modulus));

        assert_eq!(poly_ring, cmp_poly_ring);
    }

    /// Ensure that two ring elements that are instantiated the same way are equal
    #[test]
    fn same_instantiation() {
        let modulus =
            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {LARGE_PRIME}")).unwrap();
        let poly = PolyOverZq::from_str(&format!(
            "4  {} {} 1 1 mod {}",
            LARGE_PRIME + 2,
            u64::MAX,
            LARGE_PRIME
        ))
        .unwrap();

        let poly_ring_1 = PolynomialRingZq::from((&poly, &modulus));
        let poly_ring_2 = PolynomialRingZq::from((&poly, &modulus));

        assert_eq!(poly_ring_1, poly_ring_2);
    }

    /// Ensures that the function is still available for all values implementing
    /// `Into<ModulusPolynomialRingZq>`.
    #[test]
    fn availability() {
        let poly_mod = PolyOverZq::from_str("2  1 1 mod 17").unwrap();
        let modulus = ModulusPolynomialRingZq::from(&poly_mod);

        let _ = PolynomialRingZq::from((&poly_mod, &poly_mod));
        let _ = PolynomialRingZq::from((&poly_mod, poly_mod.clone()));
        let _ = PolynomialRingZq::from((poly_mod.clone(), &poly_mod));
        let _ = PolynomialRingZq::from((poly_mod.clone(), poly_mod.clone()));

        let _ = PolynomialRingZq::from((&poly_mod, &modulus));
        let _ = PolynomialRingZq::from((&poly_mod, modulus.clone()));
        let _ = PolynomialRingZq::from((poly_mod.clone(), &modulus));
        let _ = PolynomialRingZq::from((poly_mod, modulus));
    }

    /// Ensure that the function panics if the moduli mismatch.
    #[test]
    #[should_panic]
    fn mismatiching_modulus_error_borrowed() {
        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
        let poly = PolyOverZq::from_str("4  -1 0 1 1 mod 13").unwrap();

        let _ = PolynomialRingZq::from((&poly, &modulus));
    }

    /// Ensure that the function panics if the moduli mismatch.
    #[test]
    #[should_panic]
    fn mismatiching_modulus_error_owned() {
        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
        let poly = PolyOverZq::from_str("4  -1 0 1 1 mod 13").unwrap();

        let _ = PolynomialRingZq::from((poly, &modulus));
    }
}

#[cfg(test)]
mod test_from_str {
    use super::PolynomialRingZq;
    use std::str::FromStr;

    /// tests whether a falsely formatted string (integer modulus is 0) returns an
    /// error
    #[test]
    fn modulus_zero_throws_error() {
        assert!(PolynomialRingZq::from_str("4  -1 0 1 1 / 4  0 1 -2 1 mod 0").is_err());
    }

    /// tests whether a false string (negative modulus) returns an error
    #[test]
    fn false_sign() {
        assert!(PolynomialRingZq::from_str("4  0 1 -2 1 mod -42").is_err());
    }

    /// tests whether a falsely formatted string (wrong whitespaces) returns an
    /// error
    #[test]
    fn whitespaces_in_modulus() {
        assert!(PolynomialRingZq::from_str("4  -1 0 1 1 / 4  0 1 -2 1 mod 4 2").is_err());
    }

    /// tests whether a falsely formatted string (wrong symbols) returns an error
    #[test]
    fn false_format_symbols() {
        assert!(PolynomialRingZq::from_str("4  -1 0 1 1 / 1  1 mod ba").is_err());
        assert!(PolynomialRingZq::from_str("4  -1 0 1a 1 / 1  1 mod 42").is_err());
        assert!(PolynomialRingZq::from_str("4  -1 0 1 1 / b  1 mod 42").is_err());
    }

    /// tests whether a falsely formatted string (missing double-space) returns
    /// an error
    #[test]
    fn false_format() {
        assert!(PolynomialRingZq::from_str("4  -1 0 1 1 / 4 0 1 -2 1 mod 42").is_err());
        assert!(PolynomialRingZq::from_str("4 -1 0 1 1 / 4  0 1 -2 1 mod 42").is_err());
    }

    /// tests whether a falsely formatted string (wrong number of total
    /// coefficients) returns an error
    #[test]
    fn false_number_of_coefficient() {
        assert!(PolynomialRingZq::from_str("4  -1 0 1 1 / 5  0 1 -2 1 mod 42").is_err());
        assert!(PolynomialRingZq::from_str("5  -1 0 1 1 / 4  0 1 -2 1 mod 42").is_err());
    }

    /// tests whether a falsely formatted string (too many whitespaces) returns
    /// an error
    #[test]
    fn too_many_whitespaces() {
        assert!(PolynomialRingZq::from_str("4  -1  0  1  1 / 4  0  1  -2  1 mod 42").is_err());
    }

    /// Ensure that the input works with strings that have to be trimmed
    #[test]
    fn trim_input() {
        let poly = PolynomialRingZq::from_str(
            "        4  -1 0 1 1     /            4  1 2 3 1                  mod              17                     ",
        );
        assert!(poly.is_ok());
        assert_eq!(
            PolynomialRingZq::from_str("4  -1 0 1 1 / 4  1 2 3 1 mod 17").unwrap(),
            poly.unwrap()
        );
    }

    /// Ensure that a string resulting from to_string, can be used in from_str
    #[test]
    fn roundtrip() {
        let poly = PolynomialRingZq::from_str("2  1 1 / 4  1 1 -2 1 mod 42").unwrap();
        let poly2 = PolynomialRingZq::from_str(&poly.to_string()).unwrap();
        assert_eq!(poly, poly2);
    }
}