nc_polynomial/

params.rs

// MIT License
//
// Copyright (c) 2026 Raja Lehtihet & Wael El Oraiby
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
use core::fmt;
use std::sync::Arc;

use crate::polynomial::{Polynomial, PolynomialError};

/// Fixed ring settings used by cryptographic constructions over `R_q = Z_q[x] / (f(x))`.
///
/// Construction validates:
/// - polynomial metadata and modulus,
/// - modulus polynomial properties,
/// - NTT suitability for multiplying degree-bounded polynomials,
/// - primitive root compatibility with the chosen NTT length.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Params {
    max_degree: usize,
    modulus: u64,
    modulus_poly: Polynomial,
    primitive_root: u64,
    ntt_length: usize,
}

/// Errors returned while validating [`Params`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ParamsError {
    /// Underlying polynomial validation failed.
    InvalidPolynomial(PolynomialError),
    /// Modulus polynomial cannot be zero.
    ZeroModulusPolynomial,
    /// Modulus polynomial must be non-constant.
    ConstantModulusPolynomial,
    /// `degree(f)` must match `max_degree` for a consistent fixed ring shape.
    ModulusPolynomialDegreeMismatch { degree: usize, max_degree: usize },
    /// Leading coefficient of `f(x)` must be invertible in `Z_q`.
    NonInvertibleModulusPolynomialLead { coefficient: u64, modulus: u64 },
    /// Derived transform size overflowed for the selected degree bound.
    NttLengthOverflow { max_degree: usize },
    /// Derived NTT length is unsupported by the modulus (`length` must divide `q - 1`).
    NttLengthUnsupported { length: usize, modulus: u64 },
    /// Primitive root does not induce a valid root of unity for the derived NTT length.
    InvalidPrimitiveRoot {
        primitive_root: u64,
        length: usize,
        modulus: u64,
    },
}

impl fmt::Display for ParamsError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidPolynomial(err) => write!(f, "invalid polynomial parameters: {err}"),
            Self::ZeroModulusPolynomial => write!(f, "modulus polynomial cannot be zero"),
            Self::ConstantModulusPolynomial => {
                write!(f, "modulus polynomial must have degree at least 1")
            }
            Self::ModulusPolynomialDegreeMismatch { degree, max_degree } => write!(
                f,
                "modulus polynomial degree {degree} must match max_degree {max_degree}"
            ),
            Self::NonInvertibleModulusPolynomialLead {
                coefficient,
                modulus,
            } => write!(
                f,
                "modulus polynomial leading coefficient {coefficient} is not invertible modulo {modulus}"
            ),
            Self::NttLengthOverflow { max_degree } => write!(
                f,
                "failed to derive NTT length for max_degree {max_degree} due to overflow"
            ),
            Self::NttLengthUnsupported { length, modulus } => write!(
                f,
                "derived NTT length {length} is unsupported by modulus {modulus} (length must divide q-1)"
            ),
            Self::InvalidPrimitiveRoot {
                primitive_root,
                length,
                modulus,
            } => write!(
                f,
                "primitive root {primitive_root} is invalid for NTT length {length} under modulus {modulus}"
            ),
        }
    }
}

impl std::error::Error for ParamsError {}

impl Params {
    /// Builds validated ring parameters.
    ///
    /// `modulus_poly_coeffs` must define a non-constant polynomial whose degree equals
    /// `max_degree`, with invertible leading coefficient in `Z_q`.
    pub fn new(
        max_degree: usize,
        modulus: u64,
        modulus_poly_coeffs: &[u64],
        primitive_root: u64,
    ) -> Result<Self, ParamsError> {
        let modulus_poly = Polynomial::new(max_degree, modulus, modulus_poly_coeffs)
            .map_err(ParamsError::InvalidPolynomial)?;

        let Some(modulus_degree) = modulus_poly.degree() else {
            return Err(ParamsError::ZeroModulusPolynomial);
        };

        if modulus_degree == 0 {
            return Err(ParamsError::ConstantModulusPolynomial);
        }

        if modulus_degree != max_degree {
            return Err(ParamsError::ModulusPolynomialDegreeMismatch {
                degree: modulus_degree,
                max_degree,
            });
        }

        let leading = modulus_poly
            .coeff(modulus_degree)
            .expect("degree lookup must have a leading coefficient");
        if mod_inverse(leading, modulus).is_none() {
            return Err(ParamsError::NonInvertibleModulusPolynomialLead {
                coefficient: leading,
                modulus,
            });
        }

        let out_len = max_degree
            .checked_mul(2)
            .and_then(|value| value.checked_add(1))
            .ok_or(ParamsError::NttLengthOverflow { max_degree })?;
        let ntt_length = out_len
            .checked_next_power_of_two()
            .ok_or(ParamsError::NttLengthOverflow { max_degree })?;
        let ntt_length_u64 =
            u64::try_from(ntt_length).map_err(|_| ParamsError::NttLengthOverflow { max_degree })?;

        if (modulus - 1) % ntt_length_u64 != 0 {
            return Err(ParamsError::NttLengthUnsupported {
                length: ntt_length,
                modulus,
            });
        }

        let root = mod_pow(primitive_root, (modulus - 1) / ntt_length_u64, modulus);
        let is_valid_root = mod_pow(root, ntt_length_u64, modulus) == 1
            && (ntt_length == 1 || mod_pow(root, (ntt_length / 2) as u64, modulus) != 1);
        if !is_valid_root {
            return Err(ParamsError::InvalidPrimitiveRoot {
                primitive_root,
                length: ntt_length,
                modulus,
            });
        }

        Ok(Self {
            max_degree,
            modulus,
            modulus_poly,
            primitive_root,
            ntt_length,
        })
    }

    /// Maximum supported polynomial degree.
    pub fn max_degree(&self) -> usize {
        self.max_degree
    }

    /// Coefficient modulus `q`.
    pub fn modulus(&self) -> u64 {
        self.modulus
    }

    /// Ring modulus polynomial `f(x)`.
    pub fn modulus_poly(&self) -> &Polynomial {
        &self.modulus_poly
    }

    /// Primitive root used to derive NTT roots of unity.
    pub fn primitive_root(&self) -> u64 {
        self.primitive_root
    }

    /// NTT length derived from `max_degree` for exact product convolutions.
    pub fn ntt_length(&self) -> usize {
        self.ntt_length
    }
}

/// Runtime ring context that carries validated [`Params`] for operations in
/// `R_q = Z_q[x] / (f(x))`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RingContext {
    params: Arc<Params>,
}

impl RingContext {
    /// Creates a context from already-validated [`Params`].
    pub fn new(params: Params) -> Self {
        Self {
            params: Arc::new(params),
        }
    }

    /// Builds and validates parameters, then returns a context.
    pub fn from_parts(
        max_degree: usize,
        modulus: u64,
        modulus_poly_coeffs: &[u64],
        primitive_root: u64,
    ) -> Result<Self, ParamsError> {
        Ok(Self::new(Params::new(
            max_degree,
            modulus,
            modulus_poly_coeffs,
            primitive_root,
        )?))
    }

    /// Returns validated parameters.
    pub fn params(&self) -> &Params {
        self.params.as_ref()
    }

    /// Maximum supported polynomial degree.
    pub fn max_degree(&self) -> usize {
        self.params.max_degree()
    }

    /// Coefficient modulus `q`.
    pub fn modulus(&self) -> u64 {
        self.params.modulus()
    }

    /// Ring modulus polynomial `f(x)`.
    pub fn modulus_poly(&self) -> &Polynomial {
        self.params.modulus_poly()
    }

    /// Primitive root used by NTT-based operations.
    pub fn primitive_root(&self) -> u64 {
        self.params.primitive_root()
    }

    /// Derived NTT transform length.
    pub fn ntt_length(&self) -> usize {
        self.params.ntt_length()
    }

    /// Builds a polynomial compatible with this context.
    pub fn polynomial(&self, coeffs: &[u64]) -> Result<Polynomial, PolynomialError> {
        Polynomial::new(self.max_degree(), self.modulus(), coeffs)
    }

    /// Returns additive identity in this ring.
    pub fn zero(&self) -> Polynomial {
        Polynomial::zero(self.max_degree(), self.modulus())
            .expect("validated params guarantee a valid modulus")
    }

    /// Returns multiplicative identity in this ring.
    pub fn one(&self) -> Polynomial {
        Polynomial::one(self.max_degree(), self.modulus())
            .expect("validated params guarantee a valid modulus")
    }

    /// Builds a canonical ring element from coefficients by reducing modulo `f(x)`.
    pub fn element(&self, coeffs: &[u64]) -> Result<RingElem, PolynomialError> {
        let poly = self.polynomial(coeffs)?;
        self.element_from_polynomial(poly)
    }

    /// Converts a compatible polynomial into a canonical ring element.
    pub fn element_from_polynomial(&self, poly: Polynomial) -> Result<RingElem, PolynomialError> {
        self.ensure_member(&poly)?;
        RingElem::new(Arc::clone(&self.params), poly)
    }

    /// Returns additive identity as a canonical ring element.
    pub fn zero_element(&self) -> RingElem {
        self.element_from_polynomial(self.zero())
            .expect("validated params guarantee ring element creation")
    }

    /// Returns multiplicative identity as a canonical ring element.
    pub fn one_element(&self) -> RingElem {
        self.element_from_polynomial(self.one())
            .expect("validated params guarantee ring element creation")
    }

    /// Reduces polynomial modulo the configured ring polynomial.
    pub fn reduce(&self, poly: &Polynomial) -> Result<Polynomial, PolynomialError> {
        self.ensure_member(poly)?;
        poly.rem_mod_poly(self.modulus_poly())
    }

    /// Adds two ring elements and reduces modulo `f(x)`.
    pub fn add(&self, lhs: &Polynomial, rhs: &Polynomial) -> Result<Polynomial, PolynomialError> {
        self.ensure_member(lhs)?;
        self.ensure_member(rhs)?;
        lhs.add_mod_poly(rhs, self.modulus_poly())
    }

    /// Subtracts two ring elements and reduces modulo `f(x)`.
    pub fn sub(&self, lhs: &Polynomial, rhs: &Polynomial) -> Result<Polynomial, PolynomialError> {
        self.ensure_member(lhs)?;
        self.ensure_member(rhs)?;
        lhs.sub_mod_poly(rhs, self.modulus_poly())
    }

    /// Multiplies two ring elements and reduces modulo `f(x)`.
    pub fn mul(&self, lhs: &Polynomial, rhs: &Polynomial) -> Result<Polynomial, PolynomialError> {
        self.ensure_member(lhs)?;
        self.ensure_member(rhs)?;
        lhs.mul_mod_poly(rhs, self.modulus_poly())
    }

    fn ensure_member(&self, poly: &Polynomial) -> Result<(), PolynomialError> {
        if poly.max_degree() != self.max_degree() || poly.modulus() != self.modulus() {
            return Err(PolynomialError::IncompatiblePolynomials);
        }
        Ok(())
    }
}

/// Canonical element of `R_q = Z_q[x] / (f(x))`.
///
/// Each operation applies the corresponding polynomial arithmetic and then reduces modulo `f(x)`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RingElem {
    poly: Polynomial,
    params: Arc<Params>,
}

impl RingElem {
    fn new(params: Arc<Params>, poly: Polynomial) -> Result<Self, PolynomialError> {
        if poly.max_degree() != params.max_degree() || poly.modulus() != params.modulus() {
            return Err(PolynomialError::IncompatiblePolynomials);
        }

        let reduced = poly.rem_mod_poly(params.modulus_poly())?;
        Ok(Self {
            poly: reduced,
            params,
        })
    }

    /// Returns the validated parameter set that defines this element's ring.
    pub fn params(&self) -> &Params {
        self.params.as_ref()
    }

    /// Returns the underlying canonical polynomial representative.
    pub fn polynomial(&self) -> &Polynomial {
        &self.poly
    }

    /// Consumes and returns the underlying polynomial representative.
    pub fn into_polynomial(self) -> Polynomial {
        self.poly
    }

    /// Returns the dense coefficient slice of the canonical representative.
    pub fn coefficients(&self) -> &[u64] {
        self.poly.coefficients()
    }

    /// Returns coefficients trimmed to the actual degree.
    pub fn trimmed_coefficients(&self) -> Vec<u64> {
        self.poly.trimmed_coefficients()
    }

    /// Returns the representative's polynomial degree.
    pub fn degree(&self) -> Option<usize> {
        self.poly.degree()
    }

    /// Returns whether the element is additive identity.
    pub fn is_zero(&self) -> bool {
        self.poly.is_zero()
    }

    /// Adds two ring elements.
    pub fn add(&self, rhs: &Self) -> Result<Self, PolynomialError> {
        self.ensure_compatible(rhs)?;
        let poly = self
            .poly
            .add_mod_poly(&rhs.poly, self.params.modulus_poly())?;
        Ok(Self {
            poly,
            params: Arc::clone(&self.params),
        })
    }

    /// Subtracts two ring elements.
    pub fn sub(&self, rhs: &Self) -> Result<Self, PolynomialError> {
        self.ensure_compatible(rhs)?;
        let poly = self
            .poly
            .sub_mod_poly(&rhs.poly, self.params.modulus_poly())?;
        Ok(Self {
            poly,
            params: Arc::clone(&self.params),
        })
    }

    /// Multiplies two ring elements.
    pub fn mul(&self, rhs: &Self) -> Result<Self, PolynomialError> {
        self.ensure_compatible(rhs)?;
        let poly = self
            .poly
            .mul_mod_poly(&rhs.poly, self.params.modulus_poly())?;
        Ok(Self {
            poly,
            params: Arc::clone(&self.params),
        })
    }

    /// Returns additive inverse.
    pub fn neg(&self) -> Self {
        let poly = self
            .poly
            .neg()
            .rem_mod_poly(self.params.modulus_poly())
            .expect("validated params guarantee successful reduction");
        Self {
            poly,
            params: Arc::clone(&self.params),
        }
    }

    /// Multiplies by a scalar in `Z_q`.
    pub fn scalar_mul(&self, scalar: u64) -> Self {
        let poly = self
            .poly
            .scalar_mul(scalar)
            .rem_mod_poly(self.params.modulus_poly())
            .expect("validated params guarantee successful reduction");
        Self {
            poly,
            params: Arc::clone(&self.params),
        }
    }

    fn ensure_compatible(&self, rhs: &Self) -> Result<(), PolynomialError> {
        if Arc::ptr_eq(&self.params, &rhs.params) {
            return Ok(());
        }

        if self.params.as_ref() != rhs.params.as_ref() {
            return Err(PolynomialError::IncompatiblePolynomials);
        }

        Ok(())
    }
}

fn mod_mul(a: u64, b: u64, modulus: u64) -> u64 {
    ((a as u128 * b as u128) % modulus as u128) as u64
}

fn mod_pow(mut base: u64, mut exponent: u64, modulus: u64) -> u64 {
    let mut acc = 1_u64 % modulus;
    base %= modulus;

    while exponent > 0 {
        if exponent & 1 == 1 {
            acc = mod_mul(acc, base, modulus);
        }
        base = mod_mul(base, base, modulus);
        exponent >>= 1;
    }

    acc
}

fn mod_inverse(a: u64, modulus: u64) -> Option<u64> {
    let mut t = 0_i128;
    let mut new_t = 1_i128;
    let mut r = modulus as i128;
    let mut new_r = (a % modulus) as i128;

    while new_r != 0 {
        let quotient = r / new_r;
        (t, new_t) = (new_t, t - quotient * new_t);
        (r, new_r) = (new_r, r - quotient * new_r);
    }

    if r != 1 {
        return None;
    }

    if t < 0 {
        t += modulus as i128;
    }
    Some(t as u64)
}

#[cfg(test)]
mod tests {
    use super::{Params, ParamsError, RingContext};
    use crate::polynomial::PolynomialError;

    fn enumerate_ring_elements(
        ctx: &RingContext,
        values: &[u64],
        used_len: usize,
    ) -> Vec<super::RingElem> {
        assert!(
            used_len <= ctx.max_degree() + 1,
            "used_len exceeds ring capacity"
        );
        assert!(!values.is_empty(), "values cannot be empty");

        let total = values.len().pow(used_len as u32);
        let mut out = Vec::with_capacity(total);
        for mut state in 0..total {
            let mut coeffs = vec![0_u64; used_len];
            for slot in &mut coeffs {
                let digit = state % values.len();
                *slot = values[digit];
                state /= values.len();
            }
            out.push(
                ctx.element(&coeffs)
                    .expect("enumerated coefficients should build"),
            );
        }
        out
    }

    #[test]
    fn params_build_and_expose_validated_fields() {
        let params = Params::new(4, 17, &[1, 0, 0, 0, 1], 3).expect("params should validate");

        assert_eq!(params.max_degree(), 4);
        assert_eq!(params.modulus(), 17);
        assert_eq!(
            params.modulus_poly().trimmed_coefficients(),
            vec![1, 0, 0, 0, 1]
        );
        assert_eq!(params.primitive_root(), 3);
        assert_eq!(params.ntt_length(), 16);
    }

    #[test]
    fn params_reject_zero_modulus_polynomial() {
        let err = Params::new(4, 17, &[], 3).expect_err("expected error");
        assert_eq!(err, ParamsError::ZeroModulusPolynomial);
    }

    #[test]
    fn params_reject_constant_modulus_polynomial() {
        let err = Params::new(4, 17, &[3], 3).expect_err("expected error");
        assert_eq!(err, ParamsError::ConstantModulusPolynomial);
    }

    #[test]
    fn params_reject_degree_mismatch() {
        let err = Params::new(4, 17, &[1, 0, 1], 3).expect_err("expected error");
        assert_eq!(
            err,
            ParamsError::ModulusPolynomialDegreeMismatch {
                degree: 2,
                max_degree: 4,
            }
        );
    }

    #[test]
    fn params_reject_unsupported_ntt_length() {
        let err = Params::new(4, 19, &[1, 0, 0, 0, 1], 2).expect_err("expected error");
        assert_eq!(
            err,
            ParamsError::NttLengthUnsupported {
                length: 16,
                modulus: 19,
            }
        );
    }

    #[test]
    fn params_reject_invalid_primitive_root() {
        let err = Params::new(4, 17, &[1, 0, 0, 0, 1], 1).expect_err("expected error");
        assert_eq!(
            err,
            ParamsError::InvalidPrimitiveRoot {
                primitive_root: 1,
                length: 16,
                modulus: 17,
            }
        );
    }

    #[test]
    fn ring_context_applies_ring_reduction_ops() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let a = ctx
            .polynomial(&[16, 2, 0, 1, 0])
            .expect("poly should build");
        let b = ctx.polynomial(&[3, 0, 1, 0, 0]).expect("poly should build");

        let sum = ctx.add(&a, &b).expect("add should succeed");
        let diff = ctx.sub(&a, &b).expect("sub should succeed");
        let prod = ctx.mul(&a, &b).expect("mul should succeed");

        assert_eq!(sum.trimmed_coefficients(), vec![2, 2, 1, 1]);
        assert_eq!(diff.trimmed_coefficients(), vec![13, 2, 16, 1]);
        assert_eq!(prod.trimmed_coefficients(), vec![14, 5, 16, 5]);
    }

    #[test]
    fn ring_context_rejects_incompatible_members() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let foreign = RingContext::from_parts(3, 17, &[1, 0, 0, 1], 3)
            .expect("context should build")
            .one();

        let err = ctx
            .reduce(&foreign)
            .expect_err("expected incompatibility error");
        assert_eq!(err, PolynomialError::IncompatiblePolynomials);
    }

    #[test]
    fn ring_elem_creation_canonicalizes_representation() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");

        let elem = ctx
            .element(&[0, 0, 0, 0, 16])
            .expect("ring element should build");

        assert_eq!(elem.trimmed_coefficients(), vec![1]);
    }

    #[test]
    fn ring_elem_add_sub_mul_without_explicit_modulus_poly() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let a = ctx
            .element(&[16, 2, 0, 1, 0])
            .expect("ring element should build");
        let b = ctx
            .element(&[3, 0, 1, 0, 0])
            .expect("ring element should build");

        let sum = a.add(&b).expect("add should succeed");
        let diff = a.sub(&b).expect("sub should succeed");
        let prod = a.mul(&b).expect("mul should succeed");

        assert_eq!(sum.trimmed_coefficients(), vec![2, 2, 1, 1]);
        assert_eq!(diff.trimmed_coefficients(), vec![13, 2, 16, 1]);
        assert_eq!(prod.trimmed_coefficients(), vec![14, 5, 16, 5]);
    }

    #[test]
    fn ring_elem_rejects_mixed_contexts() {
        let ctx_a =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let ctx_b = RingContext::from_parts(3, 17, &[1, 0, 0, 1], 3).expect("context should build");

        let a = ctx_a.one_element();
        let b = ctx_b.one_element();

        let err = a.add(&b).expect_err("expected incompatibility error");
        assert_eq!(err, PolynomialError::IncompatiblePolynomials);
    }

    #[test]
    fn ring_elem_identity_inverse_and_scalar_laws_hold_exhaustively() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let elems = enumerate_ring_elements(&ctx, &[0, 1, 2, 3], 3);
        let zero = ctx.zero_element();
        let one = ctx.one_element();

        for elem in &elems {
            assert_eq!(elem.add(&zero).expect("e+0 should work"), *elem);
            assert_eq!(zero.add(elem).expect("0+e should work"), *elem);
            assert_eq!(elem.sub(&zero).expect("e-0 should work"), *elem);
            assert_eq!(elem.mul(&one).expect("e*1 should work"), *elem);
            assert_eq!(one.mul(elem).expect("1*e should work"), *elem);
            assert!(
                elem.add(&elem.neg()).expect("e+(-e) should work").is_zero(),
                "additive inverse should cancel"
            );
            assert_eq!(elem.scalar_mul(ctx.modulus() + 7), elem.scalar_mul(7));
            assert!(elem.scalar_mul(0).is_zero());
        }
    }

    #[test]
    fn ring_elem_ops_match_context_ops_exhaustive_small_domain() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let elems = enumerate_ring_elements(&ctx, &[0, 1, 2, 3], 3);

        for a in &elems {
            for b in &elems {
                let add_ring = a.add(b).expect("ring add should work").into_polynomial();
                let add_ctx = ctx
                    .add(a.polynomial(), b.polynomial())
                    .expect("context add should work");
                assert_eq!(add_ring, add_ctx);

                let sub_ring = a.sub(b).expect("ring sub should work").into_polynomial();
                let sub_ctx = ctx
                    .sub(a.polynomial(), b.polynomial())
                    .expect("context sub should work");
                assert_eq!(sub_ring, sub_ctx);

                let mul_ring = a.mul(b).expect("ring mul should work").into_polynomial();
                let mul_ctx = ctx
                    .mul(a.polynomial(), b.polynomial())
                    .expect("context mul should work");
                assert_eq!(mul_ring, mul_ctx);
            }
        }
    }

    #[test]
    fn ring_elem_associativity_and_distributivity_hold_on_dense_sample() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let elems = enumerate_ring_elements(&ctx, &[0, 1, 2, 3], 3);
        let sample: Vec<_> = elems.iter().take(16).cloned().collect();

        for a in &sample {
            for b in &sample {
                assert_eq!(
                    a.add(b).expect("a+b should work"),
                    b.add(a).expect("b+a should work"),
                    "addition should commute"
                );
                assert_eq!(
                    a.mul(b).expect("a*b should work"),
                    b.mul(a).expect("b*a should work"),
                    "multiplication should commute in this ring"
                );
                for c in &sample {
                    assert_eq!(
                        a.add(&b.add(c).expect("b+c should work"))
                            .expect("a+(b+c) should work"),
                        a.add(b)
                            .expect("a+b should work")
                            .add(c)
                            .expect("(a+b)+c should work"),
                        "addition should associate"
                    );
                    assert_eq!(
                        a.mul(&b.mul(c).expect("b*c should work"))
                            .expect("a*(b*c) should work"),
                        a.mul(b)
                            .expect("a*b should work")
                            .mul(c)
                            .expect("(a*b)*c should work"),
                        "multiplication should associate"
                    );
                    assert_eq!(
                        a.mul(&b.add(c).expect("b+c should work"))
                            .expect("a*(b+c) should work"),
                        a.mul(b)
                            .expect("a*b should work")
                            .add(&a.mul(c).expect("a*c should work"))
                            .expect("ab+ac should work"),
                        "left distributivity should hold"
                    );
                }
            }
        }
    }

    #[test]
    fn ring_elem_round_trips_through_polynomial_conversion() {
        let ctx =
            RingContext::from_parts(4, 17, &[1, 0, 0, 0, 1], 3).expect("context should build");
        let elems = enumerate_ring_elements(&ctx, &[0, 1, 2, 3], 3);

        for elem in elems {
            let reconstructed = ctx
                .element_from_polynomial(elem.clone().into_polynomial())
                .expect("reconstruction should work");
            assert_eq!(elem, reconstructed);
        }
    }
}