p3_field/extension/

packed_quintic_extension.rs

//! Packed quintic extension field.
//!
//! This module provides a packed version of the quintic extension field for SIMD operations.

use alloc::vec::Vec;
use core::array;
use core::iter::{Product, Sum};
use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};

use p3_util::{flatten_to_base, reconstitute_from_base};
use rand::distr::{Distribution, StandardUniform};

use super::quintic_extension::{quintic_square, trinomial_quintic_mul};
use super::{PackedExtField, QuinticTrinomialExtensionField, vector_add, vector_sub};
use crate::extension::{QuinticTrinomial, QuinticTrinomialExtendable};
use crate::{
    Algebra, BasedVectorSpace, Field, PackedField, PackedFieldExtension, PackedValue, Powers,
    PrimeCharacteristicRing, field_to_array,
};

/// Packed quintic extension field, one element per SIMD lane.
///
/// Type alias for the unified [`PackedExtField`] with `Shape = QuinticTrinomial`.
pub type PackedQuinticTrinomialExtensionField<F, PF> = PackedExtField<F, PF, 5, QuinticTrinomial>;

impl<F: Field, PF: PackedField<Scalar = F>> Default
    for PackedQuinticTrinomialExtensionField<F, PF>
{
    #[inline]
    fn default() -> Self {
        Self::new(array::from_fn(|_| PF::ZERO))
    }
}

impl<F: Field, PF: PackedField<Scalar = F>> From<QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, PF>
{
    #[inline]
    fn from(x: QuinticTrinomialExtensionField<F>) -> Self {
        Self::new(x.value.map(Into::into))
    }
}

impl<F: Field, PF: PackedField<Scalar = F>> From<PF>
    for PackedQuinticTrinomialExtensionField<F, PF>
{
    #[inline]
    fn from(x: PF) -> Self {
        Self::new(field_to_array(x))
    }
}

impl<F: Field, PF: PackedField<Scalar = F>>
    Distribution<PackedQuinticTrinomialExtensionField<F, PF>> for StandardUniform
where
    Self: Distribution<PF>,
{
    #[inline]
    fn sample<R: rand::Rng + ?Sized>(
        &self,
        rng: &mut R,
    ) -> PackedQuinticTrinomialExtensionField<F, PF> {
        PackedQuinticTrinomialExtensionField::new(array::from_fn(|_| self.sample(rng)))
    }
}

impl<F: QuinticTrinomialExtendable, PF: PackedField<Scalar = F>>
    Algebra<QuinticTrinomialExtensionField<F>> for PackedQuinticTrinomialExtensionField<F, PF>
{
}

impl<F: QuinticTrinomialExtendable, PF: PackedField<Scalar = F>> Algebra<PF>
    for PackedQuinticTrinomialExtensionField<F, PF>
{
}

impl<F, PF> PrimeCharacteristicRing for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type PrimeSubfield = PF::PrimeSubfield;

    const ZERO: Self = Self::new([PF::ZERO; 5]);

    const ONE: Self = Self::new(field_to_array(PF::ONE));

    const TWO: Self = Self::new(field_to_array(PF::TWO));

    const NEG_ONE: Self = Self::new(field_to_array(PF::NEG_ONE));

    #[inline]
    fn from_prime_subfield(val: Self::PrimeSubfield) -> Self {
        PF::from_prime_subfield(val).into()
    }

    #[inline]
    fn from_bool(b: bool) -> Self {
        PF::from_bool(b).into()
    }

    #[inline]
    fn halve(&self) -> Self {
        Self::new(self.value.map(|x| x.halve()))
    }

    #[inline(always)]
    fn square(&self) -> Self {
        let mut res = Self::default();
        quintic_square(&self.value, &mut res.value);
        res
    }

    #[inline]
    fn mul_2exp_u64(&self, exp: u64) -> Self {
        Self::new(self.value.map(|x| x.mul_2exp_u64(exp)))
    }

    #[inline]
    fn div_2exp_u64(&self, exp: u64) -> Self {
        Self::new(self.value.map(|x| x.div_2exp_u64(exp)))
    }

    #[inline]
    fn zero_vec(len: usize) -> Vec<Self> {
        // SAFETY: `Self` is `repr(transparent)` over `[PF; 5]`.
        unsafe { reconstitute_from_base(PF::zero_vec(len * 5)) }
    }
}

impl<F, PF> BasedVectorSpace<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    const DIMENSION: usize = 5;

    #[inline]
    fn as_basis_coefficients_slice(&self) -> &[PF] {
        &self.value
    }

    #[inline]
    fn from_basis_coefficients_fn<Fn: FnMut(usize) -> PF>(f: Fn) -> Self {
        Self::new(array::from_fn(f))
    }

    #[inline]
    fn from_basis_coefficients_iter<I: ExactSizeIterator<Item = PF>>(mut iter: I) -> Option<Self> {
        (iter.len() == 5).then(|| Self::new(array::from_fn(|_| iter.next().unwrap())))
    }

    #[inline]
    fn flatten_to_base(vec: Vec<Self>) -> Vec<PF> {
        // SAFETY: `Self` is `repr(transparent)` over `[PF; 5]`.
        unsafe { flatten_to_base(vec) }
    }

    #[inline]
    fn reconstitute_from_base(vec: Vec<PF>) -> Vec<Self> {
        // SAFETY: `Self` is `repr(transparent)` over `[PF; 5]`.
        unsafe { reconstitute_from_base(vec) }
    }
}

impl<F: QuinticTrinomialExtendable> PackedFieldExtension<F, QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, F::Packing>
{
    #[inline]
    fn from_ext_fn(f: impl Fn(usize) -> QuinticTrinomialExtensionField<F>) -> Self {
        Self::new(F::Packing::pack_columns_fn(|lane| f(lane).value))
    }

    #[inline]
    fn add_assign_lane(&mut self, lane: usize, value: QuinticTrinomialExtensionField<F>) {
        // Add each coefficient into its own base packing at the shared lane.
        for (coeff, v) in self.value.iter_mut().zip(value.value) {
            coeff.as_slice_mut()[lane] += v;
        }
    }

    #[inline]
    fn packed_ext_powers(base: QuinticTrinomialExtensionField<F>) -> Powers<Self> {
        let width = F::Packing::WIDTH;
        let powers = base.powers().collect_n(width + 1);
        // Transpose first WIDTH powers
        let current = Self::from_ext_slice(&powers[..width]);

        // Broadcast self^WIDTH
        let multiplier = powers[width].into();

        Powers {
            base: multiplier,
            current,
        }
    }
}

impl<F, PF> Neg for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn neg(self) -> Self {
        Self::new(self.value.map(PF::neg))
    }
}

impl<F, PF> Add for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn add(self, rhs: Self) -> Self {
        Self::new(vector_add(&self.value, &rhs.value))
    }
}

impl<F, PF> Add<QuinticTrinomialExtensionField<F>> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn add(self, rhs: QuinticTrinomialExtensionField<F>) -> Self {
        let value = vector_add(&self.value, &rhs.value);
        Self::new(value)
    }
}

impl<F, PF> Add<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn add(mut self, rhs: PF) -> Self {
        self.value[0] += rhs;
        self
    }
}

impl<F, PF> AddAssign for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn add_assign(&mut self, rhs: Self) {
        for i in 0..5 {
            self.value[i] += rhs.value[i];
        }
    }
}

impl<F, PF> AddAssign<QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn add_assign(&mut self, rhs: QuinticTrinomialExtensionField<F>) {
        for i in 0..5 {
            self.value[i] += rhs.value[i];
        }
    }
}

impl<F, PF> AddAssign<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn add_assign(&mut self, rhs: PF) {
        self.value[0] += rhs;
    }
}

impl<F, PF> Sum for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.reduce(|acc, x| acc + x).unwrap_or(Self::ZERO)
    }
}

impl<F, PF> Sub for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn sub(self, rhs: Self) -> Self {
        Self::new(vector_sub(&self.value, &rhs.value))
    }
}

impl<F, PF> Sub<QuinticTrinomialExtensionField<F>> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn sub(self, rhs: QuinticTrinomialExtensionField<F>) -> Self {
        let value = vector_sub(&self.value, &rhs.value);
        Self::new(value)
    }
}

impl<F, PF> Sub<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn sub(self, rhs: PF) -> Self {
        let mut res = self.value;
        res[0] -= rhs;
        Self::new(res)
    }
}

impl<F, PF> SubAssign for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl<F, PF> SubAssign<QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn sub_assign(&mut self, rhs: QuinticTrinomialExtensionField<F>) {
        *self = *self - rhs;
    }
}

impl<F, PF> SubAssign<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn sub_assign(&mut self, rhs: PF) {
        *self = *self - rhs;
    }
}

impl<F, PF> Mul for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn mul(self, rhs: Self) -> Self {
        let mut res = Self::default();
        trinomial_quintic_mul(&self.value, &rhs.value, &mut res.value);
        res
    }
}

impl<F, PF> Mul<QuinticTrinomialExtensionField<F>> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn mul(self, rhs: QuinticTrinomialExtensionField<F>) -> Self {
        self * Self::from(rhs)
    }
}

impl<F, PF> Mul<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[inline]
    fn mul(self, rhs: PF) -> Self {
        Self::new(self.value.map(|x| x * rhs))
    }
}

impl<F, PF> Product for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
        iter.reduce(|acc, x| acc * x).unwrap_or(Self::ONE)
    }
}

impl<F, PF> MulAssign for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl<F, PF> MulAssign<QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn mul_assign(&mut self, rhs: QuinticTrinomialExtensionField<F>) {
        *self = *self * rhs;
    }
}

impl<F, PF> MulAssign<PF> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn mul_assign(&mut self, rhs: PF) {
        *self = *self * rhs;
    }
}

impl<F, PF> Sum<QuinticTrinomialExtensionField<F>> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn sum<I: Iterator<Item = QuinticTrinomialExtensionField<F>>>(iter: I) -> Self {
        iter.map(Self::from).sum()
    }
}

impl<F, PF> Product<QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn product<I: Iterator<Item = QuinticTrinomialExtensionField<F>>>(iter: I) -> Self {
        iter.map(Self::from).product()
    }
}

impl<F, PF> Div<QuinticTrinomialExtensionField<F>> for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    type Output = Self;

    #[allow(clippy::suspicious_arithmetic_impl)]
    #[inline]
    fn div(self, rhs: QuinticTrinomialExtensionField<F>) -> Self {
        self * Self::from(rhs.inverse())
    }
}

impl<F, PF> DivAssign<QuinticTrinomialExtensionField<F>>
    for PackedQuinticTrinomialExtensionField<F, PF>
where
    F: QuinticTrinomialExtendable,
    PF: PackedField<Scalar = F>,
{
    #[inline]
    fn div_assign(&mut self, rhs: QuinticTrinomialExtensionField<F>) {
        *self = *self / rhs;
    }
}

impl<F: QuinticTrinomialExtendable> Div for PackedQuinticTrinomialExtensionField<F, F::Packing> {
    type Output = Self;

    #[allow(clippy::suspicious_arithmetic_impl)]
    #[inline]
    fn div(self, rhs: Self) -> Self {
        self * crate::invert_packed_extension::<F, QuinticTrinomialExtensionField<F>>(rhs)
    }
}

impl<F: QuinticTrinomialExtendable> DivAssign
    for PackedQuinticTrinomialExtensionField<F, F::Packing>
{
    #[inline]
    fn div_assign(&mut self, rhs: Self) {
        *self = *self / rhs;
    }
}