finitely/

lib.rs

#![doc = include_str!("../readme.md")]
#![no_std]

use core::{
    fmt::{Debug, Display, Write},
    marker::PhantomData,
    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};

use packet::Packet;

mod numerics;
mod packet;

/// A trait to configure the modulus and overflow behaviour of
/// an instance of a [`FinitePoly`].
///
/// Typically a user of this library will rarely interact with
/// this trait -- an impl for it is automatically generated by
/// the [`make_ring`] macro.
pub trait PolySettings<const SIZE: usize, const LOG2: usize>: Sized {
    /// The modulus of the base ring -- i.e. the `n` in `Z/nZ`
    ///
    /// Arithmetic in a `FinitePoly` will only ever be done in
    /// this modulus.
    const MODULO: u64;

    /// The degree of `x` which is equivalent to [`Self::OVERFLOW`].
    ///
    /// In mathematical terms, if we are building
    /// `(Z/nZ)[x]/(p(x))`, then this is `deg(p)`.
    const DEGREE: usize;

    /// This is equivalent to `x` raised to the power of
    /// [`Self::DEGREE`].
    ///
    /// In mathematical terms, if we are building
    /// `(Z/nZ)[x]/(p(x))` then:
    /// ```text
    /// p(x) = x^DEGREE - OVERFLOW(x)
    /// ```
    /// So that:
    /// ```text
    /// p(x) = 0 ==> x^DEGREE = OVERFLOW(x)
    /// ```
    const OVERFLOW: FinitePoly<Self, SIZE, LOG2>;
}

/// An element of a Quotient Ring Of a Polynomial Ring
///
/// This structure implements arithmetic in the ring:
/// `(Z/nZ)[x]/(p(x))`. Precisely what this means is covered
/// in the crate docs, written in plain and accessible language.
///
/// Generic Parameters:
/// - `T` is a type which controls the Modulus of coefficients
///   and Overflow behaviour on `x`.
/// - `SIZE` is the number of `u64`s required to represent the
///   first bit of every coefficient in any polynomial. This
///   value should be `T::DEGREE.div_ceil(64)`.
/// - `LOG2` is the number of bits required to represent any
///   coefficient in the polynomial. For example, if the modulus
///   is 5, `LOG2` is 3, since 4 is a possible coefficient and
///   is represented as 100 in binary.
///
/// Example usage:
/// ```
/// use finitely::make_ring;
/// make_ring! {
///     F9 = { Z % 3, x^2 = [2] };
/// }    
///
/// let value = F9::from_coeffs(&[1, 2]);
/// assert_eq!(format!("{value}"), String::from("x + 2"));
///
/// // (x + 2) + (x + 2) = 2x + 4 = 2x + 1 (mod 3).
/// assert_eq!(value + value, F9::from_coeffs(&[2, 1]));
///
/// // (x + 2) * (x + 2) = x^2 + 4x + 4 = x^2 + x + 1 (mod 3).
/// // Since x^2 = 2, we get x + 1 + 2 = x (mod 3).
/// assert_eq!(value * value, F9::from_coeffs(&[1, 0]));
/// ```
pub struct FinitePoly<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> {
    pub(crate) internal: [Packet<LOG2>; SIZE],
    pub(crate) _phantom: PhantomData<T>,
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Eq
    for FinitePoly<T, SIZE, LOG2>
{
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> PartialEq
    for FinitePoly<T, SIZE, LOG2>
{
    fn eq(&self, other: &Self) -> bool {
        Self::eq(*self, *other)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> PartialEq<u64>
    for FinitePoly<T, SIZE, LOG2>
{
    fn eq(&self, other: &u64) -> bool {
        self.degree() == 0 && (self.get_nth_coeff(0) % T::MODULO) == *other
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Copy
    for FinitePoly<T, SIZE, LOG2>
{
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Clone
    for FinitePoly<T, SIZE, LOG2>
{
    fn clone(&self) -> Self {
        *self
    }
}

/// Throughout the examples in this implementation block,
/// we will be using the example ring:
/// ```
/// use finitely::make_ring;
/// make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
/// ```
impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> FinitePoly<T, SIZE, LOG2> {
    /// The zero polynomial.
    pub const ZERO: Self = Self {
        internal: [Packet::<LOG2>::new(); SIZE],
        _phantom: PhantomData,
    };

    const FALSE_ZERO: Packet<LOG2> = Packet::splat(T::MODULO as u64 % (1u64 << LOG2));
    const OVERFLOW: Packet<LOG2> = Packet::splat((1u64 << LOG2) % T::MODULO as u64);
    const DEGREE_OVERFLOW_BIT: usize = T::DEGREE - 1 - Self::DEGREE_OVERFLOW_U64 * 64;
    const DEGREE_OVERFLOW_U64: usize = (T::DEGREE - 1) / 64;
    const FILTER_EXCESS_BITS: u64 =
        (1 << Self::DEGREE_OVERFLOW_BIT) | ((1 << Self::DEGREE_OVERFLOW_BIT) - 1);

    /// The one polynomial.
    pub const ONE: Self = Self::from_int(1);

    /// Creates a polynomial where every coefficient
    /// is `value`. I.e. `value + value x + value x^2 + ...`.
    ///
    /// This runs in *`O(LOG2 * SIZE)`*
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// ```
    pub const fn splat(value: u64) -> Self {
        Self {
            internal: [Packet::splat(value); SIZE],
            _phantom: PhantomData,
        }
    }

    /// Is equivalent to representing `value` as a degree-0
    /// polynomial. Mathematically speaking, this is equivalent
    /// to adding 1 a total of `value` times.
    ///
    /// Note that this is _not_ implemented by adding 1 a total
    /// of `value` times.
    ///
    /// This runs in *`O(LOG2 * SIZE)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::from_int(2), F25::ONE + F25::ONE);
    /// assert_eq!(F25::from_int(5), F25::ZERO);
    /// ```
    pub const fn from_int(value: u64) -> Self {
        let mut me = Self::ZERO;
        me.internal[0] = Packet::from_int(value % T::MODULO);

        me
    }

    /// A useful function when debugging the internals of this
    /// library. Unlikely to be useful to a user, if all methods
    /// on this type have been implemented correctly.
    ///
    /// Removes "false zeros" -- coefficients which are equal
    /// to our modulus and are not zero as a result of arithmetic.
    ///
    /// For example, if we are working modulo 5, then we need
    /// 3 bits. If you ask `finite` to compute `1 + 1 + 1 + 1 + 1`
    /// modulo 5, then it will represent the coefficient internally
    /// as `101`, as reduction modulo the modulus is done
    /// as lazily as possible in the space given. When acquiring
    /// the coefficient through `get_nth_coeff`, it will
    /// automatically be reduced modulo the modulus.
    const fn remove_false_zeros(mut self) -> Self {
        let mut done = 0;

        while done < SIZE {
            let temp = self.internal[done];

            // xor detects any differences with a false zero.
            // or reduction accumulates any differences into a single u64.
            // where there was a difference is now a 1, where there was
            // not (i.e. it is a false zero) is now a 0.
            let zeros_detect = temp.xor(Self::FALSE_ZERO).or_reduce();

            // and-ing will remove elements where zeros_detect is 0
            // which are places where we have a false zero.
            self.internal[done] = temp.and_u64(zeros_detect);

            done += 1;
        }

        self
    }

    /// Computes the degree of this polynomial.
    ///
    /// Mathematically speaking, it computes the smallest degree
    /// of any representative of the equivalence class after reducing
    /// modulo `p`.
    ///
    /// This runs in *`O(LOG2 * SIZE)`*
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::ZERO.degree(), 0);
    /// assert_eq!(F25::ONE.degree(), 0);
    /// assert_eq!(F25::from_coeffs(&[1, 2]).degree(), 1);
    /// ```
    pub const fn degree(mut self) -> usize {
        self = self.remove_false_zeros();

        let mut done = 1;

        while done <= SIZE {
            let mut to_detect = self.internal[SIZE - done];

            if done == SIZE {
                to_detect = to_detect.and_u64(Self::FILTER_EXCESS_BITS);
            }

            let leading = to_detect.leading_zeros();
            let first_one_idx = 64 - leading;

            if first_one_idx != 0 {
                let degree_total = first_one_idx + (SIZE - done) as u64 * 64;

                return degree_total as usize - 1;
            }

            done += 1;
        }

        0
    }

    /// Computes whether `self` is equivalent to `other`.
    ///
    /// This runs in *`O(?)`*
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// let value_1 = F25::from_coeffs(&[2, 1]);
    /// let value_2 = F25::from_coeffs(&[1, 0]);
    /// let product = F25::from_coeffs(&[3, 1]);
    /// assert!((value_1 * value_2).eq(product));
    /// ```
    pub const fn eq(self, other: Self) -> bool {
        let diff = self.sub(other);

        diff.is_zero()
    }

    /// Computes whether `self` is the zero polynomial.
    ///
    /// This runs in *`O(LOG2 * SIZE)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert!(F25::ZERO.is_zero());
    /// assert!(!F25::ONE.is_zero());
    /// let fake_5 = F25::ONE + F25::ONE + F25::ONE + F25::ONE + F25::ONE;
    /// assert!(fake_5.is_zero());
    /// ```
    pub const fn is_zero(mut self) -> bool {
        self = self.remove_false_zeros();
        let mut done = 0;

        while done < SIZE - 1 {
            if self.internal[done].or_reduce() != 0 {
                return false;
            }

            done += 1;
        }

        if self.internal[SIZE - 1].or_reduce() << (64 - T::DEGREE % 64) != 0 {
            return false;
        }

        true
    }

    /// Runs in at most *`O(LOG2^2)`*.
    ///
    /// I need to verify that is the lowest upper bound.
    const fn add_within(n: Packet<LOG2>, m: Packet<LOG2>) -> Packet<LOG2> {
        let mut result = n;
        let mut carry = m;
        let mut overflow_carry = Packet::new();

        while !carry.is_zero() || !overflow_carry.is_zero() {
            let add = result.xor(carry).xor(overflow_carry);
            // new_carry = (result & carry) | (result & overflow_carry) | (carry & overflow_carry).
            // That simplifies to this:
            let new_carry = result
                .and(carry.or(overflow_carry))
                .or(carry.and(overflow_carry));

            let (bumped, new_carry) = new_carry.left_shift_horizontal();

            let new_overflow = Self::OVERFLOW.and_u64(bumped);

            result = add;
            carry = new_carry;
            overflow_carry = new_overflow;
        }

        result
    }

    /// Computes the sum of `self` with `other`.
    ///
    /// Note: this type implements [`std::ops::Add`].
    ///
    /// This adds coefficient-wise.
    ///
    /// This runs in *`O(LOG2^2 * SIZE)`*
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::ONE.add(F25::ONE), F25::from_int(2));
    /// assert_eq!(F25::from_int(4).add(F25::ONE), 0);
    /// ```
    pub const fn add(mut self, other: Self) -> Self {
        let mut i = 0;
        while i < SIZE {
            self.internal[i] = Self::add_within(self.internal[i], other.internal[i]);
            i += 1;
        }

        self
    }

    /// Essentially the same thing as add_within.
    /// This has the same time complexity.
    const fn sub_within(n: Packet<LOG2>, m: Packet<LOG2>) -> Packet<LOG2> {
        let mut result = n;
        let mut carry = m;
        let mut underflow_carry = Packet::new();

        while !carry.is_zero() || !underflow_carry.is_zero() {
            let sub = result.xor(carry).xor(underflow_carry);

            let new_carry = result
                .not()
                .and(carry.or(underflow_carry))
                .or(carry.and(underflow_carry));

            let (bumped, new_carry) = new_carry.left_shift_horizontal();

            let new_underflow = Self::OVERFLOW.and_u64(bumped);

            result = sub;
            carry = new_carry;
            underflow_carry = new_underflow;
        }

        result
    }

    /// Computes the difference between `self` and `other`.
    ///
    /// Note: this type implements [`std::ops::Sub`].
    ///
    /// This subtracts component-wise.
    ///
    /// This runs in *`O(LOG2^2 * SIZE)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::from_int(3) - 1, 2);
    /// assert_eq!(F25::ZERO - F25::ONE, 4);
    /// ```
    pub const fn sub(mut self, other: Self) -> Self {
        let mut i = 0;
        while i < SIZE {
            self.internal[i] = Self::sub_within(self.internal[i], other.internal[i]);
            i += 1;
        }

        self
    }

    /// Essentially computes `0 - n`.
    /// This runs in O(LOG2^2) at worst.
    const fn neg_within(n: Packet<LOG2>) -> Packet<LOG2> {
        let mut result = n;
        let mut carry = n;
        let bumped;

        (bumped, carry) = carry.left_shift_horizontal();

        let mut underflow_carry = Self::OVERFLOW.and_u64(bumped);

        while !carry.is_zero() || !underflow_carry.is_zero() {
            let sub = result.xor(carry).xor(underflow_carry);

            let new_carry = result
                .not()
                .and(carry.or(underflow_carry))
                .or(carry.and(underflow_carry));

            let (bumped, new_carry) = new_carry.left_shift_horizontal();

            let new_underflow = Self::OVERFLOW.and_u64(bumped);

            result = sub;
            carry = new_carry;
            underflow_carry = new_underflow;
        }

        result
    }

    /// Computes the negation modulo the modulus of the polynomial.
    ///
    /// Note: this type implements [`std::ops::Neg`].
    ///
    /// Since all coefficients are positive, a coefficient `c` is
    /// transformed into `MODULO - c`, which is equivalent to `-c`
    /// modulo `MODULO`.
    ///
    /// This runs in *`O(LOG2^2 * SIZE)`*
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::from_coeffs(&[2, 3]).neg(), F25::from_coeffs(&[3, 2]));
    /// ```
    pub const fn neg(mut self) -> Self {
        let mut i = 0;

        while i < SIZE {
            self.internal[i] = Self::neg_within(self.internal[i]);

            i += 1;
        }

        self
    }

    /// Computes `self` times a constant coefficient.
    ///
    /// Note: this type implements [`std::ops::Mul`].
    ///
    /// This is faster than multiplying by `FinitePoly::make_int(by)`
    /// since this can take advantage that the degree of the polynomial
    /// will not change (unless you set `by = 0`, but that doesn't change
    /// anything).
    ///
    /// This runs in *`O(LOG2^3 * SIZE)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(
    ///     F25::from_coeffs(&[2, 4]).mul_modulo(2),
    ///     F25::from_coeffs(&[4, 3])
    /// );
    /// ```
    pub const fn mul_modulo(self, by: u64) -> Self {
        let mut by = by % T::MODULO as u64;

        let mut acc = Self::ZERO;
        let mut power_2 = self;

        while by != 0 {
            if by & 1 == 1 {
                acc = acc.add(power_2);
            }

            by >>= 1;
            power_2 = power_2.add(power_2);
        }

        acc
    }

    /// Computes `self` times `x` and reduces.
    ///
    /// This runs in *`O(LOG2^3 * SIZE)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::ONE.mul_x(), F25::from_coeffs(&[1, 0]));
    /// assert_eq!(F25::ONE.mul_x().mul_x(), F25::from_coeffs(&[1, 3]));
    /// assert_eq!(F25::from_coeffs(&[4, 2]).mul_x(), F25::from_coeffs(&[1, 2]));
    /// ```
    pub const fn mul_x(mut self) -> Self {
        let extracted_overflow =
            self.internal[Self::DEGREE_OVERFLOW_U64].extract_coefficient(Self::DEGREE_OVERFLOW_BIT);

        let overflow = T::OVERFLOW.mul_modulo(extracted_overflow);

        self = self.unchecked_mulx(1);

        self.add(overflow)
    }

    /// Multiplies `self` by `x` without doing overflow.
    ///
    /// This runs in *`O(LOG2 * SIZE)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::ONE.unchecked_mulx(2), 0);
    /// ```
    pub const fn unchecked_mulx(mut self, power: usize) -> Self {
        if power == 0 {
            return self;
        }
        let mut done = 0;

        let mut carry = Packet::new();

        while done != SIZE {
            let new_carry = self.internal[done].rsh(64 - power);
            self.internal[done] = self.internal[done].lsh(power).or(carry);

            carry = new_carry;
            done += 1;
        }

        self
    }

    /// Acquires the nth coefficient of the polynomial.
    ///
    /// This runs in *`O(LOG2)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// let value = F25::from_coeffs(&[2, 3]);
    /// assert_eq!(value.get_nth_coeff(0), 3);
    /// assert_eq!(value.get_nth_coeff(1), 2);
    /// ```
    pub const fn get_nth_coeff(self, coeff: usize) -> u64 {
        if coeff >= T::DEGREE {
            return 0;
        }

        let u64_idx = coeff / 64;
        let within_u64_idx = coeff % 64;

        self.internal[u64_idx].extract_coefficient(within_u64_idx)
    }

    /// Sets a coefficient in the polynomial.
    ///
    /// This runs in *`O(LOG2)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// let value = F25::ZERO.set_coeff(0, 3).set_coeff(1, 2);
    /// assert_eq!(value.get_nth_coeff(0), 3);
    /// assert_eq!(value.get_nth_coeff(1), 2);
    /// ```
    #[must_use = "Since this method is const and cannot take &mut, you must assign it to a new variable."]
    pub const fn set_coeff(mut self, idx: usize, coeff: u64) -> Self {
        if idx >= T::DEGREE {
            return self;
        }

        let u64_idx = idx / 64;
        let within_u64_idx = idx % 64;

        self.internal[u64_idx] = self.internal[u64_idx].set_coeff(within_u64_idx, coeff);

        self
    }

    /// Computes the multiplication of `self` with `other`, reducing
    /// modulo `p(x)` (the overflow is applied), and of course reducing
    /// modulo `MODULO`.
    ///
    /// This runs in *`O(SIZE^2 * LOG2^3)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// let value_1 = F25::from_coeffs(&[1, 4]);
    /// let value_2 = F25::from_coeffs(&[2, 3]);
    /// assert_eq!(value_1 * value_2, value_2 * value_1);
    /// assert_eq!(value_1 * value_2, F25::from_coeffs(&[3, 3]));
    /// ```
    pub const fn mul(self, other: Self) -> Self {
        let mut acc = Self::ZERO;
        let mut power_x = self;

        let mut powers_done = 0;

        while powers_done < T::DEGREE {
            let coeff = other.get_nth_coeff(powers_done);

            if coeff != 0 {
                if coeff == 1 {
                    acc = acc.add(power_x);
                } else {
                    acc = acc.add(power_x.mul_modulo(coeff));
                }
            }

            power_x = power_x.mul_x();

            powers_done += 1;
        }

        acc
    }

    /// If possible, returns self/other, self - other * self/other.
    ///
    /// This is sometimes possible if `MODULO` is not prime.
    ///
    /// This runs in *`O(SIZE^2 * LOG2^3)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// let numerator = F25::from_coeffs(&[1, 2]);
    /// let denominator = F25::from_coeffs(&[1, 4]);
    ///
    /// let (division, remainder) = numerator.divide_remainder(denominator).unwrap();
    /// assert_eq!(division, 1);  
    /// assert_eq!(remainder, 3);  
    /// // x + 2 == 1 * (x + 4) + 3
    /// ```
    pub const fn divide_remainder(self, other: Self) -> Option<(Self, Self)> {
        let other_degree = other.degree();

        let mut quotient = Self::ZERO;
        let mut remainder = self;

        let mut remainder_degree = remainder.degree();

        while other_degree <= remainder_degree && !remainder.is_zero() {
            let difference_in_degree = remainder_degree - other_degree;
            // println!("Quotient: {quotient}, Remainder: {remainder}, diff: {difference_in_degree}, self: {self}, other: {other}");
            let my_coeff = remainder.get_nth_coeff(remainder_degree);
            let other_coeff = other.get_nth_coeff(other_degree);

            let Some(inverse) = numerics::divide_modulo(T::MODULO, my_coeff, other_coeff) else {
                return None;
            };

            let division = Self::from_int(inverse).unchecked_mulx(difference_in_degree);
            quotient = quotient.add(division);

            let product = other
                .mul_modulo(inverse)
                .unchecked_mulx(difference_in_degree);

            remainder = remainder.sub(product);

            remainder_degree = remainder.degree();
        }

        Some((quotient, remainder))
    }

    /// Computes the same thing as [`Self::divide_remainder`], however
    /// the parameters are `(p(x), self)`. Since you cannot represent
    /// `p(x)` using this ring (it will reduce to `OVERFLOW`), this
    /// specialized function is necessary.
    ///
    /// This runs in *`O(SIZE^2 * LOG2^3)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// // Our quotient poly is x^2 + 4x + 2.
    /// let denominator = F25::from_coeffs(&[1, 3]);     // x + 3
    ///
    /// let (quotient, remainder) = denominator.divide_quotient_poly_by_self().unwrap();
    /// assert_eq!(quotient, F25::from_coeffs(&[1, 1])); // x + 1
    /// assert_eq!(remainder, F25::from_coeffs(&[4]));   // 4
    ///
    /// // See: (x + 1)(x + 3) + 4 == x^2 + 4x + 2.
    /// ```
    pub const fn divide_quotient_poly_by_self(self) -> Option<(Self, Self)> {
        let my_degree = T::DEGREE;
        let other_degree = self.degree();

        let difference_in_degree = my_degree - other_degree;
        let other_coeff = self.get_nth_coeff(other_degree);

        let Some(inverse) = numerics::invert_in_modulo(T::MODULO, other_coeff) else {
            return None;
        };

        let division = if difference_in_degree == T::DEGREE {
            return Some((Self::ZERO.sub(T::OVERFLOW).mul_modulo(inverse), Self::ZERO));
        } else {
            Self::from_int(inverse).unchecked_mulx(difference_in_degree)
        };

        let to_remove = self.set_coeff(other_degree, 0);

        let product = to_remove.mul(division);

        let remainder = Self::ZERO.sub(T::OVERFLOW).sub(product);

        let Some((new_division, remainder)) = remainder.divide_remainder(self) else {
            return None;
        };

        Some((division.add(new_division), remainder))
    }

    /// Tries to find a multiplicative inverse in the ring.
    ///
    /// That is, it will (try to) find an element `x` such
    /// that `self.mul(x) == Self::ONE`.
    ///
    /// This will always succeed if `self` is a nonzero element
    /// of `Self` and `Self` is a field. That is, if `MODULO` is
    /// a prime number, and `p(x) = x^DEGREE - OVERFLOW(x)` is
    /// irreducible modulo `MODULO`.
    ///
    /// If you are not over a field, this is only guaranteed to work
    /// for constants, and the results for non-constant members of
    /// the a non-field is unspecified.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::from_int(3).invert().unwrap(), 2);
    /// assert_eq!(F25::ONE.mul_x().invert().unwrap(), F25::from_coeffs(&[2, 3]));
    /// // Notice: x(2x + 3) = 1.
    /// ```
    pub const fn invert(self) -> Option<Self> {
        let mut t = Self::ZERO;
        let mut r;
        let mut new_t = Self::ONE;
        let mut new_r = self;

        // `r` should actually be x^degree - T::OVERFLOW = p(x).
        // However, we cannot represent that number, so instead
        // we use the special case function to compute p(x)/self.

        let Some((quotient, remainder)) = self.divide_quotient_poly_by_self() else {
            return None;
        };

        (r, new_r) = (new_r, remainder);
        (t, new_t) = (new_t, t.sub(quotient.mul(new_t)));

        while !new_r.is_zero() {
            let Some((quotient, remainder)) = Self::divide_remainder(r, new_r) else {
                return None;
            };

            (r, new_r) = (new_r, remainder);
            (t, new_t) = (new_t, t.sub(quotient.mul(new_t)));
        }

        if r.degree() > 0 {
            return None;
        }

        let r_as_integer = r.get_nth_coeff(0);
        let Some(inverse) = numerics::invert_in_modulo(T::MODULO, r_as_integer) else {
            return None;
        };

        Some(t.mul_modulo(inverse))
    }

    /// Constructs a polynomial given the specified coefficients.
    ///
    /// This runs in *`O(SIZE * LOG2)`*.
    ///
    /// Example usage:
    /// ```
    /// # use finitely::make_ring;
    /// # make_ring! { F25 = { Z % 5, x^2 = [1, 3] }; }
    /// assert_eq!(F25::from_coeffs(&[2, 1]), F25::from_coeffs(&[7, 6]));
    /// ```
    pub const fn from_coeffs(mut coeffs: &[u64]) -> Self {
        let to_do = if coeffs.len() > T::DEGREE {
            T::DEGREE
        } else {
            coeffs.len()
        };

        (_, coeffs) = coeffs.split_at(coeffs.len() - to_do);

        let last_block_length = coeffs.len() % 64;

        let (last_block, mut coeffs) = coeffs.split_at(last_block_length);

        let last_block = Packet::from_coeffs(last_block);

        let mut acc = Self::ZERO;

        let mut insertion_idx = 0;

        while coeffs.len() != 0 {
            let (rest, last) = coeffs.split_at(coeffs.len() - 64);

            coeffs = rest;

            acc.internal[insertion_idx] = Packet::from_coeffs(last);

            insertion_idx += 1;
        }

        acc.internal[insertion_idx] = last_block;

        acc
    }

    /// Writes a debug version of `self` to `w`.
    pub fn format_full(self, mut w: impl Write) -> core::fmt::Result {
        for i in (1..T::DEGREE).rev() {
            let coeff = self.get_nth_coeff(i) % T::MODULO as u64;

            write!(w, "{coeff}x^{i} + ")?;
        }

        write!(w, "{}", self.get_nth_coeff(0) % T::MODULO as u64)
    }

    /// Writes a display version of `self` to `w`.
    pub fn format_filtered(self, mut w: impl Write) -> core::fmt::Result {
        if self == Self::ZERO {
            return write!(w, "0");
        }

        let mut seen_first = false;

        for i in (1..T::DEGREE).rev() {
            let coeff = self.get_nth_coeff(i) % T::MODULO as u64;

            if coeff != 0 {
                if seen_first {
                    write!(w, " + ")?;
                } else {
                    seen_first = true;
                }

                if coeff != 1 {
                    write!(w, "{coeff}")?;
                }

                write!(w, "x")?;

                if i != 1 {
                    write!(w, "^{i}")?;
                }
            }
        }

        let zeroth = self.get_nth_coeff(0) % T::MODULO as u64;

        if zeroth != 0 {
            if seen_first {
                write!(w, " + {zeroth}")?;
            } else {
                write!(w, "{zeroth}")?;
            }
        }

        Ok(())
    }

    /// Returns an iterator over all members of the field.
    pub fn iter() -> FinitePolyIterator<T, SIZE, LOG2> {
        FinitePolyIterator {
            coeffs: Some(Self::ZERO),
            _item: PhantomData,
        }
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Debug
    for FinitePoly<T, SIZE, LOG2>
{
    fn fmt(&self, mut f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        self.format_full(&mut f)?;
        write!(f, " [")?;
        for val in self.internal[1..].iter().rev() {
            write!(f, "{val}, ")?;
        }
        write!(f, "{}", self.internal[0])?;
        write!(f, "]")
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Display
    for FinitePoly<T, SIZE, LOG2>
{
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        self.format_filtered(f)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Mul<Self>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn mul(self, rhs: Self) -> Self {
        self.mul(rhs)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Mul<u64>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn mul(self, rhs: u64) -> Self {
        self.mul_modulo(rhs)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Div<Self>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn div(self, rhs: Self) -> Self {
        self * rhs.invert().unwrap()
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Div<u64>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn div(self, rhs: u64) -> Self {
        self * Self::from_int(rhs).invert().unwrap()
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Add<Self>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn add(self, rhs: Self) -> Self {
        self.add(rhs)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Add<u64>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn add(self, rhs: u64) -> Self {
        self.add(Self::from_int(rhs))
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Neg
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn neg(self) -> Self {
        self.neg()
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Sub<Self>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn sub(self, rhs: Self) -> Self {
        self.sub(rhs)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Sub<u64>
    for FinitePoly<T, SIZE, LOG2>
{
    type Output = Self;

    fn sub(self, rhs: u64) -> Self {
        self.sub(Self::from_int(rhs))
    }
}

impl<T: PolySettings<SIZE, LOG2>, U, const SIZE: usize, const LOG2: usize> AddAssign<U>
    for FinitePoly<T, SIZE, LOG2>
where
    Self: Add<U, Output = Self>,
{
    fn add_assign(&mut self, rhs: U) {
        *self = *self + rhs;
    }
}

impl<T: PolySettings<SIZE, LOG2>, U, const SIZE: usize, const LOG2: usize> SubAssign<U>
    for FinitePoly<T, SIZE, LOG2>
where
    Self: Sub<U, Output = Self>,
{
    fn sub_assign(&mut self, rhs: U) {
        *self = *self - rhs;
    }
}

impl<T: PolySettings<SIZE, LOG2>, U, const SIZE: usize, const LOG2: usize> MulAssign<U>
    for FinitePoly<T, SIZE, LOG2>
where
    Self: Mul<U, Output = Self>,
{
    fn mul_assign(&mut self, rhs: U) {
        *self = *self * rhs;
    }
}

impl<T: PolySettings<SIZE, LOG2>, U, const SIZE: usize, const LOG2: usize> DivAssign<U>
    for FinitePoly<T, SIZE, LOG2>
where
    Self: Div<U, Output = Self>,
{
    fn div_assign(&mut self, rhs: U) {
        *self = *self / rhs;
    }
}

/// Iterates over all of the elements of the finite ring.
///
/// Created by calling [`FinitePoly::iter`].
pub struct FinitePolyIterator<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> {
    coeffs: Option<FinitePoly<T, SIZE, LOG2>>,
    _item: PhantomData<FinitePoly<T, SIZE, LOG2>>,
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> Iterator
    for FinitePolyIterator<T, SIZE, LOG2>
{
    type Item = FinitePoly<T, SIZE, LOG2>;

    fn next(&mut self) -> Option<Self::Item> {
        let coeffs = self.coeffs?;
        let mut new_coeffs = coeffs;

        let mut is_zero = true;

        for i in 0..T::DEGREE {
            let elem = new_coeffs.get_nth_coeff(i);

            let mut new_val = elem + 1;

            let carry = new_val / T::MODULO as u64;
            new_val -= carry * T::MODULO as u64;

            new_coeffs = new_coeffs.set_coeff(i, new_val);

            is_zero &= new_val == 0;

            if carry == 0 {
                break;
            }
        }

        if is_zero {
            self.coeffs = None;
        } else {
            self.coeffs = Some(new_coeffs);
        }

        Some(coeffs)
    }
}

impl<T: PolySettings<SIZE, LOG2>, const SIZE: usize, const LOG2: usize> From<u64>
    for FinitePoly<T, SIZE, LOG2>
{
    fn from(value: u64) -> Self {
        Self::from_int(value)
    }
}

const fn log2(x: u64) -> usize {
    (64 - (x - 1).leading_zeros()) as _
}

/// Returns the number of `u64`-width packets to represent the
/// polynomials given by `T::DEGREE`.
pub const fn get_size<T: PolySettings<0, 0>>() -> usize {
    T::DEGREE.div_ceil(64)
}

/// Returns the number of bits required to represent coefficients
/// modulo `T::MODULO`.
pub const fn get_log2<T: PolySettings<0, 0>>() -> usize {
    log2(T::MODULO)
}

#[doc(hidden)]
#[macro_export]
#[allow(unused_macros)]
macro_rules! forward_const {
    (
        $view:vis, ($t:ty) :
        $(
            fn $name:ident($($param_name:ident $(* $idx:literal)? $(: $param_ty:ty)?),*) -> $ret_ty:ident$(<$generics:ident>)?;
        )*
    ) => {
        $(
            #[allow(dead_code)]
            $view const fn $name($($param_name $(: $param_ty)?),*) -> $ret_ty$(<$generics>)? {
                $crate::forward_const!(@result : ($ret_ty) : (<$t>::$name($($crate::forward_const!(@param: $param_name $(* $idx)?)),*)))
            }
        )*
    };

    (@param: $n:ident * $idx:literal) => {$n.0};
    (@param: $($t:tt)*) => {$($t)*};
    (@result: (Self) : ($($t:tt)*)) => {Self($($t)*)};
    (@result: (Option) : ($($t:tt)*)) => {match $($t)* { Some(x) => Some(Self(x)), None => None }};
    (@result: ($($t0:tt)*) : ($($t:tt)*)) => {$($t)*};
}

#[doc(hidden)]
#[macro_export]
#[allow(unused_macros)]
macro_rules! forward_op_impl {
    (@basic: $on:ty: $($name:ident -- $method:ident ($op:tt) $other:ident $(*$lit:literal)?),*) => {
        
$(
        
    $crate::forward_op_impl!{@basic_inner: $on ; $name ; $method ; ($op) ; $other $(*$lit)?}
        
)*
    };
    (@basic_inner: $on:ty ; $name:ident ; $method:ident ; ($op:tt) ; $other:ident $(* $lit:literal)?) => {
        impl ::core::ops::$name<$other> for $on {
            type Output = Self;

            fn $method(self, other: $other) -> Self {
                Self(self.0 $op $crate::forward_const!(@param: other $(* $lit)?))
            }
        }
    };

    (@assign: $on:ty: $($name:ident -- $method:ident $other:ident $(*$lit:literal)?),*) => {
        $(
            $crate::forward_op_impl!{@assign_inner: $on ; $name ; $method ; $other $(*$lit)?}
        )*
    };
    (@assign_inner: $on:ty ; $name:ident ; $method:ident ; $other:ident $(* $lit:literal)?) => {
        impl ::core::ops::$name<$other> for $on {
            fn $method(&mut self, other: $other) {
                self.0.$method($crate::forward_const!(@param: other $(* $lit)?))
            }
        }
    };
}

/// Creates a newtype with the necessary trait forwards for ease-of-use.
///
/// Example usage:
/// ```
/// use finitely::make_ring;
///
/// make_ring! {
///     // Attributes are supported:
///
///     #[allow(dead_code)]
///     /// The field with 25 elements.
///     pub(crate) F25 = { Z % 5, x^2 = [3] };
///
///     WeirdRing = { Z % 3500, x^5 = [12, 3, 4, 56] };
/// }
/// ```
#[allow(unused_macros)]
#[macro_export]
macro_rules! make_ring {
    ($($(#[$at:meta])* $view:vis $name:ident = { Z % $modulo:literal, x^ $degree:literal = [$($coefficients:literal),+] };)+) => {$(
        $(#[$at])*
        #[derive(PartialEq, Copy, Clone)]
        $view struct $name($crate::FinitePoly<Self, {$crate::get_size::<Self>()}, {$crate::get_log2::<Self>()}>);

        impl<const SIZE: usize, const LOG2: usize> $crate::PolySettings<SIZE, LOG2> for $name {
            const DEGREE: usize = $degree;
            const MODULO: u64 = $modulo;

            const OVERFLOW: $crate::FinitePoly<Self, SIZE, LOG2> = $crate::FinitePoly::<Self, SIZE, LOG2>::from_coeffs(&[$($coefficients),+]);
        }

        impl $name {
            #[allow(dead_code)]
            $view const LOG2: usize = $crate::get_size::<Self>();
            #[allow(dead_code)]
            $view const SIZE: usize = $crate::get_log2::<Self>();
            #[allow(dead_code)]
            $view const OVERFLOW: Self = Self(<Self as $crate::PolySettings<{Self::LOG2}, {Self::SIZE}>>::OVERFLOW);

            $view const ZERO: Self = Self($crate::FinitePoly::<Self, {$crate::get_size::<Self>()}, {$crate::get_log2::<Self>()}>::ZERO);
            $view const ONE: Self = Self($crate::FinitePoly::<Self, {$crate::get_size::<Self>()}, {$crate::get_log2::<Self>()}>::ONE);

            $crate::forward_const! {
                $view, ($crate::FinitePoly<Self, {$crate::get_size::<Self>()}, {$crate::get_log2::<Self>()}>) :
                fn splat(value: u64) -> Self;
                fn from_int(value: u64) -> Self;
                fn degree(self*0) -> usize;
                fn eq(self*0, other*0: Self) -> bool;
                fn is_zero(self*0) -> bool;
                fn add(self*0, other*0: Self) -> Self;
                fn sub(self*0, other*0: Self) -> Self;
                fn mul(self*0, other*0: Self) -> Self;
                fn neg(self*0) -> Self;
                fn mul_modulo(self*0, by: u64) -> Self;
                fn mul_x(self*0) -> Self;
                fn unchecked_mulx(self*0, power: usize) -> Self;
                fn get_nth_coeff(self*0, coeff: usize) -> u64;
                fn set_coeff(self*0, idx: usize, coeff: u64) -> Self;
                fn invert(self*0) -> Option<Self>;
                fn from_coeffs(coeffs: &[u64]) -> Self;
            }

            #[allow(dead_code)]
            $view const fn divide_remainder(self, other: Self) -> Option<(Self, Self)> {
                match self.0.divide_remainder(other.0) {
                    Some((x, y)) => Some((Self(x), Self(y))),
                    None => None
                }
            }

            #[allow(dead_code)]
            $view const fn divide_quotient_poly_by_self(self) -> Option<(Self, Self)> {
                match self.0.divide_quotient_poly_by_self() {
                    Some((x, y)) => Some((Self(x), Self(y))),
                    None => None
                }
            }

            $view fn iter() -> impl Iterator<Item = Self> {
                $crate::FinitePoly::<Self, {$crate::get_size::<Self>()}, {$crate::get_log2::<Self>()}>::iter().map(|x| Self(x))
            }
        }

        const _: () = {
            type Poly = $crate::FinitePoly<$name, {$crate::get_size::<$name>()}, {$crate::get_log2::<$name>()}>;
            impl From<$name> for Poly {
                fn from(other: $name) -> Self {
                    other.0
                }
            }

            impl From<Poly> for $name {
                fn from(other: Poly) -> Self {
                    Self(other)
                }
            }

            impl ::core::fmt::Debug for $name {
                fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> ::core::fmt::Result {
                    <Poly as ::core::fmt::Debug>::fmt(&self.0, f)
                }
            }

            impl ::core::fmt::Display for $name {
                fn fmt(&self, f: &mut ::core::fmt::Formatter<'_>) -> ::core::fmt::Result {
                    <Poly as ::core::fmt::Display>::fmt(&self.0, f)
                }
            }

            impl ::core::cmp::Eq for $name {}

            impl<T> ::core::cmp::PartialEq<T> for $name
            where Poly: PartialEq<T> {
                fn eq(&self, other: &T) -> bool {
                    self.0 == *other
                }
            }

            $crate::forward_op_impl! {
                @basic: $name:
                Add -- add (+) u64,
                Add -- add (+) Poly,
                Add -- add (+) $name * 0,
                Sub -- sub (-) u64,
                Sub -- sub (-) Poly,
                Sub -- sub (-) $name * 0,
                Mul -- mul (*) u64,
                Mul -- mul (*) Poly,
                Mul -- mul (*) $name * 0,
                Div -- div (/) u64,
                Div -- div (/) Poly,
                Div -- div (/) $name * 0
            }

            $crate::forward_op_impl! {
                @assign: $name:
                AddAssign -- add_assign u64,
                AddAssign -- add_assign Poly,
                AddAssign -- add_assign $name * 0,
                SubAssign -- sub_assign u64,
                SubAssign -- sub_assign Poly,
                SubAssign -- sub_assign $name * 0,
                MulAssign -- mul_assign u64,
                MulAssign -- mul_assign Poly,
                MulAssign -- mul_assign $name * 0,
                DivAssign -- div_assign u64,
                DivAssign -- div_assign Poly,
                DivAssign -- div_assign $name * 0
            }
        };
    )+};
}

#[cfg(test)]
mod tests {
    macro_rules! make_ring_tests {
        ($name:ident, $coeffs:literal, $modulo:literal) => {
            #[test]
            fn integer_to_poly() {
                let one_const = $name::ONE;
                let one_phi = $name::from_int(1);

                assert_eq!(one_const, one_phi);

                for i in 0..20 {
                    let pre_reduced = i % $modulo;

                    let value_1 = $name::from_int(i);
                    let value_2 = $name::from_int(pre_reduced);
                    let mut value_3 = $name::ZERO;

                    for _ in 0..i {
                        value_3 = value_3 + $name::ONE;
                    }

                    let mut value_4 = $name::ZERO;

                    for _ in 0..pre_reduced {
                        value_4 = value_4 + $name::ONE;
                    }

                    assert_eq!(value_1, value_2);
                    assert_eq!(value_2, value_3);
                    assert_eq!(value_3, value_4);
                }
            }

            #[test]
            fn coeff_equality() {
                for lhs in $name::iter() {
                    for rhs in $name::iter() {
                        let mut equal = true;
                        for power in 0..$coeffs {
                            let coeff_left = lhs.get_nth_coeff(power) % $modulo;
                            let coeff_right = rhs.get_nth_coeff(power) % $modulo;

                            equal &= coeff_left == coeff_right;
                        }

                        assert_eq!(equal, lhs == rhs, "Lhs: {lhs}, Rhs: {rhs}");
                    }
                }
            }

            #[test]
            fn equality_is_equality() {
                // An equivalence relation ~ satisfies:
                // 1. x ~ x
                // 2. x ~ y ==> y ~ x
                // 3. x ~ y and y ~ z ==> x ~ z

                // Test identity.
                for x in $name::iter() {
                    assert_eq!(x, x);
                }

                // Test reflexivity.
                for x in $name::iter() {
                    for y in $name::iter() {
                        assert_eq!(x == y, y == x);
                    }
                }

                // Test transitivity.
                for x in $name::iter() {
                    for y in $name::iter() {
                        for z in $name::iter() {
                            if x == y && y == z {
                                assert_eq!(x, z);
                            }
                        }
                    }
                }
            }

            // We happen to have a field. The field axioms are:
            // 1.  Exists `+: F x F -> F` (done.)
            // 2.  Exists `*: F x F -> F` (done.)
            // 3.  For all: `x + y = y + x`.
            // 4.  For all: `x * y = y * x`.
            // 5.  For all: `x + (y + z) = (x + y) + z`
            // 6.  For all: `x * (y * z) = (x * y) * z`
            // 7.  Exists `0 in F`: For all: `x + 0 = x`.
            // 8.  Exists `1 in F`: For all: `x * 1 = x`.
            // 9.  For all: `x * (y + z) = x * y + x * z`.
            // 10. For all `x in F`: Exists `y in F`: `x + y = 0`
            // The previous 10 give us a Commutative Unital Ring
            // (from now on, this is just a ring). These two extra
            // axioms make it a field:
            // 11. `0 != 1`.
            // 12. For all `x in F`: `x != y` implies Exists `y in F`: `x * y = 1`

            #[test]
            fn addition_commutes() {
                for x in $name::iter() {
                    for y in $name::iter() {
                        assert_eq!(x + y, y + x);
                    }
                }
            }

            #[test]
            fn multiplication_commutes() {
                for x in $name::iter() {
                    for y in $name::iter() {
                        assert_eq!(x * y, y * x);
                    }
                }
            }

            #[test]
            fn addition_associates() {
                for x in $name::iter() {
                    for y in $name::iter() {
                        for z in $name::iter() {
                            assert_eq!(x + (y + z), (x + y) + z);
                        }
                    }
                }
            }

            #[test]
            fn multiplication_associates() {
                for x in $name::iter() {
                    for y in $name::iter() {
                        for z in $name::iter() {
                            assert_eq!(x * (y * z), (x * y) * z);
                        }
                    }
                }
            }

            #[test]
            fn zero_is_zero() {
                for x in $name::iter() {
                    assert_eq!(x + $name::ZERO, x);
                }
            }

            #[test]
            fn one_is_one() {
                for x in $name::iter() {
                    assert_eq!(x * $name::ONE, x);
                }
            }

            #[test]
            fn multiplication_distributes() {
                for x in $name::iter() {
                    for y in $name::iter() {
                        for z in $name::iter() {
                            assert_eq!(x * (y + z), (x * y) + (x * z));
                        }
                    }
                }
            }

            #[test]
            fn additive_inverses() {
                'a: for x in $name::iter() {
                    for y in $name::iter() {
                        if x + y == $name::ZERO {
                            continue 'a;
                        }
                    }

                    panic!("Additive inverse for {x} not found!");
                }
            }

            #[test]
            fn zero_is_not_one() {
                assert_ne!($name::ZERO, $name::ONE);
            }
        };
    }

    make_ring! {
        F125 = { Z % 5, x^3 = [2, 2] };
        BadRingSmall = { Z % 6, x^1 = [0] };
        BadRing = { Z % 6, x^2 = [3, 2] };
        BadPoly = { Z % 5, x^2 = [4] };
    }

    mod field {
        use super::F125;
        make_ring_tests! {F125, 3, 5}

        #[test]
        fn multiplicative_inverse() {
            for x in F125::iter() {
                let computed_inverse = x.invert();

                let mut found_inverse = None;
                for y in F125::iter() {
                    if x * y == F125::ONE {
                        found_inverse = Some(y);
                        break;
                    }
                }

                assert_eq!(computed_inverse, found_inverse, "Poly: {x}");

                if !x.is_zero() && computed_inverse.is_none() {
                    panic!("Multiplicative inverse for {x} not found!");
                }
            }
        }
    }

    mod integers_bad {
        use super::BadRingSmall;
        make_ring_tests! {BadRingSmall, 1, 6}

        #[test]
        fn integers_mod_bad() {
            for (i, val) in BadRingSmall::iter().enumerate() {
                assert_eq!(val, BadRingSmall::from_int(i as u64));
            }
        }
    }

    mod integers_bad_poly_bad {
        use super::BadRing;
        make_ring_tests! {BadRing, 2, 6}
    }

    mod poly_bad {
        use super::BadPoly;
        make_ring_tests! {BadPoly, 2, 5}
    }
}