vsss-rs 6.0.0

//! Represents Galois Field of 2^4 elements. This uses constant time operations
//! for all operations as related to shamir secret sharing. Too many implementations
//! use lookup tables which help for speed but leak secret information.
//! No lookup tables are used in this implementation because Cryptographic operations should
//!
//! 1. Ensure runtime is independent of secret data
//! 2. Ensure code access patterns are independent of secret data
//! 3. Ensure data access patterns are independent of secret data

use crate::util::{CtIsNotZero, field_bounded_add, uniform_nonzero_u8};
use crate::*;
use core::borrow::Borrow;
use core::{
    fmt::{self, Binary, Display, Formatter, LowerHex, UpperHex},
    iter::{Product, Sum},
    ops::{
        Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Deref,
        DerefMut, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign,
    },
};
use ff::{Field, PrimeField};
use rand_core::TryRng;
use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};

#[cfg(any(feature = "alloc", feature = "std"))]
use crate::ParticipantIdGenerator;
use rand_core::CryptoRng;
#[cfg(feature = "zeroize")]
use zeroize::DefaultIsZeroes;

#[cfg(any(feature = "alloc", feature = "std"))]
type GfShare = DefaultShare<IdentifierGf16, IdentifierGf16>;

/// Represents the finite field GF(2^4) with 16 elements.
/// Elements are stored in the lower nibble of a u8 (values 0x00..=0x0F).
/// Uses the irreducible polynomial x^4 + x + 1 for multiplication.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(transparent)]
pub struct Gf16(pub u8);

#[cfg(feature = "zeroize")]
impl DefaultIsZeroes for Gf16 {}

impl Display for Gf16 {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl LowerHex for Gf16 {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(f, "{:01x}", self.0)
    }
}

impl UpperHex for Gf16 {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(f, "{:01X}", self.0)
    }
}

impl Binary for Gf16 {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(f, "{:04b}", self.0)
    }
}

impl ConditionallySelectable for Gf16 {
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        Gf16(u8::conditional_select(&a.0, &b.0, choice))
    }
}

impl ConstantTimeEq for Gf16 {
    fn ct_eq(&self, other: &Self) -> Choice {
        self.0.ct_eq(&other.0)
    }
}

impl Add for Gf16 {
    type Output = Self;

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

impl Add<&Gf16> for Gf16 {
    type Output = Gf16;

    fn add(self, rhs: &Gf16) -> Gf16 {
        self + *rhs
    }
}

impl Add<Gf16> for &Gf16 {
    type Output = Gf16;

    fn add(self, rhs: Gf16) -> Gf16 {
        *self + rhs
    }
}

impl Add<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn add(self, rhs: &Gf16) -> Gf16 {
        *self + *rhs
    }
}

impl AddAssign for Gf16 {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl AddAssign<&Gf16> for Gf16 {
    fn add_assign(&mut self, rhs: &Gf16) {
        *self = *self + *rhs;
    }
}

impl Sub for Gf16 {
    type Output = Self;

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

impl Sub<&Gf16> for Gf16 {
    type Output = Gf16;

    fn sub(self, rhs: &Gf16) -> Gf16 {
        Gf16(self.0 ^ rhs.0)
    }
}

impl Sub<Gf16> for &Gf16 {
    type Output = Gf16;

    fn sub(self, rhs: Gf16) -> Gf16 {
        Gf16(self.0 ^ rhs.0)
    }
}

impl Sub<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn sub(self, rhs: &Gf16) -> Gf16 {
        Gf16(self.0 ^ rhs.0)
    }
}

impl SubAssign for Gf16 {
    fn sub_assign(&mut self, rhs: Self) {
        self.0 ^= rhs.0;
    }
}

impl SubAssign<&Gf16> for Gf16 {
    fn sub_assign(&mut self, rhs: &Gf16) {
        self.0 ^= rhs.0;
    }
}

impl Mul for Gf16 {
    type Output = Self;

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

impl Mul<&Gf16> for Gf16 {
    type Output = Gf16;

    fn mul(self, rhs: &Gf16) -> Gf16 {
        self * *rhs
    }
}

impl Mul<Gf16> for &Gf16 {
    type Output = Gf16;

    fn mul(self, rhs: Gf16) -> Gf16 {
        *self * rhs
    }
}

impl Mul<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn mul(self, rhs: &Gf16) -> Gf16 {
        *self * *rhs
    }
}

impl MulAssign for Gf16 {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl MulAssign<&Gf16> for Gf16 {
    fn mul_assign(&mut self, rhs: &Gf16) {
        *self = *self * *rhs;
    }
}

impl Div for Gf16 {
    type Output = Self;

    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.invert().expect("no division by zero")
    }
}

impl Div<&Gf16> for Gf16 {
    type Output = Gf16;

    fn div(self, rhs: &Gf16) -> Gf16 {
        self / *rhs
    }
}

impl Div<Gf16> for &Gf16 {
    type Output = Gf16;

    fn div(self, rhs: Gf16) -> Gf16 {
        *self / rhs
    }
}

impl Div<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn div(self, rhs: &Gf16) -> Gf16 {
        *self / *rhs
    }
}

impl DivAssign for Gf16 {
    fn div_assign(&mut self, rhs: Self) {
        *self *= rhs.invert().expect("no division by zero");
    }
}

impl DivAssign<&Gf16> for Gf16 {
    fn div_assign(&mut self, rhs: &Gf16) {
        *self *= rhs.invert().expect("no division by zero");
    }
}

impl Neg for Gf16 {
    type Output = Self;

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

impl BitAnd for Gf16 {
    type Output = Self;

    fn bitand(self, rhs: Self) -> Self {
        Self(self.0 & rhs.0)
    }
}

impl BitAnd<&Gf16> for Gf16 {
    type Output = Gf16;

    fn bitand(self, rhs: &Gf16) -> Gf16 {
        self & *rhs
    }
}

impl BitAnd<Gf16> for &Gf16 {
    type Output = Gf16;

    fn bitand(self, rhs: Gf16) -> Gf16 {
        *self & rhs
    }
}

impl BitAnd<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn bitand(self, rhs: &Gf16) -> Gf16 {
        *self & *rhs
    }
}

impl BitAndAssign for Gf16 {
    fn bitand_assign(&mut self, rhs: Self) {
        self.0 &= rhs.0;
    }
}

impl BitAndAssign<&Gf16> for Gf16 {
    fn bitand_assign(&mut self, rhs: &Gf16) {
        self.0 &= rhs.0;
    }
}

impl BitOr for Gf16 {
    type Output = Self;

    fn bitor(self, rhs: Self) -> Self {
        Self(self.0 | rhs.0)
    }
}

impl BitOr<&Gf16> for Gf16 {
    type Output = Gf16;

    fn bitor(self, rhs: &Gf16) -> Gf16 {
        self | *rhs
    }
}

impl BitOr<Gf16> for &Gf16 {
    type Output = Gf16;

    fn bitor(self, rhs: Gf16) -> Gf16 {
        *self | rhs
    }
}

impl BitOr<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn bitor(self, rhs: &Gf16) -> Gf16 {
        *self | *rhs
    }
}

impl BitOrAssign for Gf16 {
    fn bitor_assign(&mut self, rhs: Self) {
        self.0 |= rhs.0;
    }
}

impl BitOrAssign<&Gf16> for Gf16 {
    fn bitor_assign(&mut self, rhs: &Gf16) {
        self.0 |= rhs.0;
    }
}

impl BitXor for Gf16 {
    type Output = Self;

    fn bitxor(self, rhs: Self) -> Self {
        Self(self.0 ^ rhs.0)
    }
}

impl BitXor<&Gf16> for Gf16 {
    type Output = Gf16;

    fn bitxor(self, rhs: &Gf16) -> Gf16 {
        self ^ *rhs
    }
}

impl BitXor<Gf16> for &Gf16 {
    type Output = Gf16;

    fn bitxor(self, rhs: Gf16) -> Gf16 {
        *self ^ rhs
    }
}

impl BitXor<&Gf16> for &Gf16 {
    type Output = Gf16;

    fn bitxor(self, rhs: &Gf16) -> Gf16 {
        *self ^ *rhs
    }
}

impl BitXorAssign for Gf16 {
    fn bitxor_assign(&mut self, rhs: Self) {
        self.0 ^= rhs.0;
    }
}

impl BitXorAssign<&Gf16> for Gf16 {
    fn bitxor_assign(&mut self, rhs: &Gf16) {
        self.0 ^= rhs.0;
    }
}

impl<T: Borrow<Gf16>> Sum<T> for Gf16 {
    fn sum<I: Iterator<Item = T>>(iter: I) -> Self {
        iter.fold(Self(0), |acc, x| acc + x.borrow())
    }
}

impl<T: Borrow<Gf16>> Product<T> for Gf16 {
    fn product<I: Iterator<Item = T>>(iter: I) -> Self {
        iter.fold(Self(1), |acc, x| acc * x.borrow())
    }
}

impl Field for Gf16 {
    const ZERO: Self = Self(0);
    const ONE: Self = Self(1);

    fn try_random<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
        // Uniform over the full field {0, 1, ..., 15}. The prior
        // `(b & 0x0E) + 1` forced the low bit and yielded only odd
        // nibbles {1,3,...,15}; that bias leaks into polynomial
        // coefficients used by Shamir secret sharing (audit finding #1).
        rng.try_next_u32().map(|v| Self(v as u8 & 0x0F))
    }

    fn square(&self) -> Self {
        self * self
    }

    fn double(&self) -> Self {
        self + self
    }

    fn invert(&self) -> CtOption<Self> {
        // Compute a^(2^4 - 2) = a^14 = a^(-1) in GF(2^4).
        // Loop pattern: after k iterations, z = a^(2^(k+1) - 1).
        // After 2 iterations: z = a^7. Final square: a^14.
        let mut z = self.0;
        for _ in 0..2 {
            z = gf16_mul(z, z);
            z = gf16_mul(z, self.0);
        }
        CtOption::new(Self(gf16_mul(z, z)), self.0.ct_is_not_zero())
    }

    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
        let p = 0xfu8; // |GF(16)*| = 15
        let pm1d2 = (p - 1) >> 1; // 7
        let pp2d4 = (p + 2) >> 2; // 4

        // z = 2 (x) is a primitive root: gf16_pow(2, 7) = 11 != 1
        let z = (2..=p).find(|z| gf16_pow(*z, pm1d2) != 1).unwrap();

        let a = gf16_mul(num.0, div.0);
        let mut c = gf16_pow(a, pp2d4);
        let mut t = gf16_pow(a, pm1d2);
        let mut r = gf16_pow(z, pm1d2);

        let mut m = t;
        let mut i = 1usize;
        while m != 1 && m != 0 {
            let mut temp = m;
            for _ in 1..i {
                temp = gf16_mul(temp, temp);
            }
            let mut j = 0usize;
            while temp != 1 && temp != 0 && j < 4 {
                temp = gf16_mul(temp, temp);
                j += 1;
            }
            if i <= j {
                break;
            }
            let b = gf16_pow(r, 1u8 << (i - j - 1));
            c = gf16_mul(c, b);
            r = gf16_mul(b, b);
            t = gf16_mul(t, r);
            m = t;
            i = j;
        }
        let is_square = gf16_pow(c, 2).ct_eq(&c);
        (is_square, Self(c))
    }
}

impl From<u8> for Gf16 {
    fn from(val: u8) -> Self {
        Gf16(val)
    }
}

impl From<Gf16> for u8 {
    fn from(val: Gf16) -> u8 {
        val.0
    }
}

impl From<u16> for Gf16 {
    fn from(val: u16) -> Self {
        Gf16(val as u8)
    }
}

impl From<Gf16> for u16 {
    fn from(val: Gf16) -> u16 {
        val.0 as u16
    }
}

impl From<u32> for Gf16 {
    fn from(val: u32) -> Self {
        Gf16(val as u8)
    }
}

impl From<Gf16> for u32 {
    fn from(val: Gf16) -> u32 {
        val.0 as u32
    }
}

impl From<u64> for Gf16 {
    fn from(val: u64) -> Self {
        Gf16(val as u8)
    }
}

impl From<Gf16> for u64 {
    fn from(val: Gf16) -> u64 {
        val.0 as u64
    }
}

impl From<u128> for Gf16 {
    fn from(val: u128) -> Self {
        Gf16(val as u8)
    }
}

impl From<Gf16> for u128 {
    fn from(val: Gf16) -> u128 {
        val.0 as u128
    }
}

impl PrimeField for Gf16 {
    type Repr = [u8; 1];

    fn from_repr(repr: Self::Repr) -> CtOption<Self> {
        CtOption::new(Self(repr[0]), Choice::from(1u8))
    }

    fn to_repr(&self) -> Self::Repr {
        [self.0]
    }

    fn is_odd(&self) -> Choice {
        (self.0 & 1).ct_eq(&1)
    }

    const MODULUS: &'static str = "";
    const NUM_BITS: u32 = 4;
    const CAPACITY: u32 = 3;
    /// TWO_INV = 2^(-1) in GF(2^4): 2 * 9 = 1, so TWO_INV = 9.
    const TWO_INV: Self = Self(9);
    /// x = 2 is a primitive root of GF(2^4): powers of 2 generate all 15 non-zero elements.
    const MULTIPLICATIVE_GENERATOR: Self = Self(2);
    /// S = 0 since |GF(16)*| = 15 is odd (2-adic valuation of 15 is 0).
    const S: u32 = 0;
    /// The 2^S = 1-st root of unity is 1 (trivially).
    const ROOT_OF_UNITY: Self = Self(1);
    const ROOT_OF_UNITY_INV: Self = Self(1);
    /// DELTA = MULTIPLICATIVE_GENERATOR^(2^S) = 2^1 = 2.
    const DELTA: Self = Self(2);
}

impl Gf16 {
    /// Raise the element to the power of `exp` in GF(2^4).
    pub fn pow(&self, exp: u8) -> Self {
        Self(gf16_pow(self.0, exp))
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Split a byte array into shares using GF(2^4) arithmetic.
    ///
    /// Each input byte is treated as two 4-bit nibbles (low = bits 0-3, high = bits 4-7).
    /// Both nibbles are independently shared as GF(16) elements and packed back into
    /// a single share byte, preserving the 1:1 byte ratio between secret and share data.
    /// Maximum of 15 shares (the field has 15 non-zero elements).
    pub fn split_array<B: AsRef<[u8]>>(
        threshold: usize,
        limit: usize,
        secret: B,
        rng: impl CryptoRng,
    ) -> VsssResult<Vec<Vec<u8>>> {
        Self::split_array_with_participant_generators(
            threshold,
            limit,
            secret,
            rng,
            &[ParticipantIdGenerator::default()],
        )
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Split bytes into shares using GF(2^4) arithmetic.
    pub fn split_bytes<B: AsRef<[u8]>>(
        threshold: usize,
        limit: usize,
        secret: B,
        rng: impl CryptoRng,
    ) -> VsssResult<Vec<Vec<u8>>> {
        Self::split_array(threshold, limit, secret, rng)
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Split a byte array into shares using the participant number generator.
    pub fn split_array_with_participant_generators<B: AsRef<[u8]>>(
        threshold: usize,
        limit: usize,
        secret: B,
        mut rng: impl CryptoRng,
        participant_generators: &[ParticipantIdGenerator<IdentifierGf16>],
    ) -> VsssResult<Vec<Vec<u8>>> {
        if limit > 15 {
            return Err(Error::InvalidSizeRequest);
        }
        let secret = secret.as_ref();
        if secret.is_empty() {
            return Err(Error::InvalidSecret);
        }
        let mut shares = Vec::with_capacity(limit);
        let mut ids = Vec::with_capacity(limit);

        let collection = ParticipantIdGeneratorCollection::from(participant_generators);
        let mut participant_id_iter = collection.iter();

        for _ in 0..limit {
            let id = participant_id_iter
                .next()
                .ok_or(Error::NotEnoughShareIdentifiers)?;
            let mut inner = Vec::with_capacity(secret.len() + 1);
            inner.push(id.0.0);
            ids.push(id);
            shares.push(inner);
        }
        check_params(threshold, limit)?;
        let mut lo_polynomial = <Vec<GfShare> as Polynomial<GfShare>>::create(threshold);
        let mut hi_polynomial = <Vec<GfShare> as Polynomial<GfShare>>::create(threshold);
        for b in secret {
            // Each byte is split into two nibbles and shared independently.
            // The low nibble and high nibble are each a GF(16) element (0..=15).
            let lo = IdentifierGf16(Gf16(*b & 0x0f));
            let hi = IdentifierGf16(Gf16((*b >> 4) & 0x0f));

            lo_polynomial.fill(&lo, &mut rng, threshold)?;
            hi_polynomial.fill(&hi, &mut rng, threshold)?;
            // Pack both nibble-shares into a single byte per participant.
            for (share, id) in shares.iter_mut().zip(ids.iter()) {
                let mut lo_value = IdentifierGf16::default();
                let mut hi_value = IdentifierGf16::default();
                lo_polynomial.evaluate_in_place(id, threshold, &mut lo_value);
                hi_polynomial.evaluate_in_place(id, threshold, &mut hi_value);
                let lo_s = lo_value.0.0;
                let hi_s = hi_value.0.0;
                share.push((hi_s << 4) | lo_s);
            }
        }
        Ok(shares)
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Split bytes into shares using participant number generators.
    pub fn split_bytes_with_participant_generators<B: AsRef<[u8]>>(
        threshold: usize,
        limit: usize,
        secret: B,
        rng: impl CryptoRng,
        participant_generators: &[ParticipantIdGenerator<IdentifierGf16>],
    ) -> VsssResult<Vec<Vec<u8>>> {
        Self::split_array_with_participant_generators(
            threshold,
            limit,
            secret,
            rng,
            participant_generators,
        )
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Split bytes into shares using an iterator of participant identifiers.
    pub fn split_bytes_with_participant_ids_iter<B, I>(
        threshold: usize,
        limit: usize,
        secret: B,
        mut rng: impl CryptoRng,
        participant_ids: I,
    ) -> VsssResult<Vec<Vec<u8>>>
    where
        B: AsRef<[u8]>,
        I: IntoIterator<Item = IdentifierGf16>,
    {
        if limit > 15 {
            return Err(Error::InvalidSizeRequest);
        }
        let secret = secret.as_ref();
        if secret.is_empty() {
            return Err(Error::InvalidSecret);
        }
        check_params(threshold, limit)?;

        let mut shares = Vec::with_capacity(limit);
        let mut ids = Vec::with_capacity(limit);
        let mut participant_id_iter = participant_ids.into_iter();

        for _ in 0..limit {
            let id = participant_id_iter
                .next()
                .ok_or(Error::NotEnoughShareIdentifiers)?;
            if id.is_zero().into() {
                return Err(Error::SharingInvalidIdentifier);
            }
            let mut inner = Vec::with_capacity(secret.len() + 1);
            inner.push(id.0.0);
            ids.push(id);
            shares.push(inner);
        }

        let mut lo_polynomial = <Vec<GfShare> as Polynomial<GfShare>>::create(threshold);
        let mut hi_polynomial = <Vec<GfShare> as Polynomial<GfShare>>::create(threshold);
        for b in secret {
            let lo = IdentifierGf16(Gf16(*b & 0x0f));
            let hi = IdentifierGf16(Gf16((*b >> 4) & 0x0f));

            lo_polynomial.fill(&lo, &mut rng, threshold)?;
            hi_polynomial.fill(&hi, &mut rng, threshold)?;
            for (share, id) in shares.iter_mut().zip(ids.iter()) {
                let mut lo_value = IdentifierGf16::default();
                let mut hi_value = IdentifierGf16::default();
                lo_polynomial.evaluate_in_place(id, threshold, &mut lo_value);
                hi_polynomial.evaluate_in_place(id, threshold, &mut hi_value);
                let lo_s = lo_value.0.0;
                let hi_s = hi_value.0.0;
                share.push((hi_s << 4) | lo_s);
            }
        }
        Ok(shares)
    }

    #[cfg(feature = "stream")]
    #[cfg_attr(docsrs, doc(cfg(feature = "stream")))]
    /// Split bytes into shares using an asynchronous stream of participant identifiers.
    ///
    /// Exactly `limit` identifiers are consumed. Returns
    /// [`Error::NotEnoughShareIdentifiers`] if the stream ends early.
    pub async fn split_bytes_with_participant_ids_stream<B>(
        threshold: usize,
        limit: usize,
        secret: B,
        rng: impl CryptoRng,
        participant_ids: impl futures_core::Stream<Item = IdentifierGf16>,
    ) -> VsssResult<Vec<Vec<u8>>>
    where
        B: AsRef<[u8]>,
    {
        if limit > 15 {
            return Err(Error::InvalidSizeRequest);
        }
        if secret.as_ref().is_empty() {
            return Err(Error::InvalidSecret);
        }
        check_params(threshold, limit)?;
        let participant_ids =
            collect_stream_exact(limit, participant_ids, Error::NotEnoughShareIdentifiers).await?;
        Self::split_bytes_with_participant_ids_iter(threshold, limit, secret, rng, participant_ids)
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Combine shares into a byte array.
    pub fn combine_array<B: AsRef<[Vec<u8>]>>(shares: B) -> VsssResult<Vec<u8>> {
        let shares = shares.as_ref();

        Self::are_shares_valid(shares)?;

        let mut secret = Vec::with_capacity(shares[0].len() - 1);
        let coefficients = lagrange_coefficients(shares)?;
        for i in 1..shares[0].len() {
            let mut lo = IdentifierGf16(Gf16(0u8));
            let mut hi = IdentifierGf16(Gf16(0u8));
            for (share, coefficient) in shares.iter().zip(coefficients.iter()) {
                let lo_term = IdentifierGf16(Gf16(share[i] & 0x0f)) * coefficient;
                let hi_term = IdentifierGf16(Gf16((share[i] >> 4) & 0x0f)) * coefficient;
                *lo.as_mut() += lo_term.as_ref();
                *hi.as_mut() += hi_term.as_ref();
            }
            secret.push(((hi.0.0 & 0x0f) << 4) | (lo.0.0 & 0x0f));
        }
        Ok(secret)
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    /// Combine shares into bytes.
    pub fn combine_bytes<B: AsRef<[Vec<u8>]>>(shares: B) -> VsssResult<Vec<u8>> {
        Self::combine_array(shares)
    }

    /// Combine an iterator of owned byte shares.
    #[cfg(any(feature = "alloc", feature = "std"))]
    pub fn combine_bytes_iter(shares: impl IntoIterator<Item = Vec<u8>>) -> VsssResult<Vec<u8>> {
        let shares: Vec<_> = shares.into_iter().collect();
        Self::combine_bytes(shares)
    }

    /// Combine exactly `share_count` byte shares from an asynchronous stream.
    ///
    /// Returns [`Error::NotEnoughShares`] if the stream ends before yielding
    /// `share_count` shares. Items after `share_count` are left in the stream.
    #[cfg(feature = "stream")]
    #[cfg_attr(docsrs, doc(cfg(feature = "stream")))]
    pub async fn combine_bytes_stream(
        share_count: usize,
        shares: impl futures_core::Stream<Item = Vec<u8>>,
    ) -> VsssResult<Vec<u8>> {
        if share_count < 2 {
            return Err(Error::SharingMinThreshold);
        }
        let shares = collect_stream_exact(share_count, shares, Error::NotEnoughShares).await?;
        Self::combine_bytes(shares)
    }

    /// Combine exactly `share_count` byte shares from an asynchronous stream.
    ///
    /// This is an alias for [`Gf16::combine_bytes_stream`].
    #[cfg(feature = "stream")]
    #[cfg_attr(docsrs, doc(cfg(feature = "stream")))]
    pub async fn combine_array_stream(
        share_count: usize,
        shares: impl futures_core::Stream<Item = Vec<u8>>,
    ) -> VsssResult<Vec<u8>> {
        Self::combine_bytes_stream(share_count, shares).await
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    fn are_shares_valid(shares: &[Vec<u8>]) -> VsssResult<()> {
        if shares.len() < 2 {
            return Err(Error::SharingMinThreshold);
        }
        if shares[0].len() < 2 {
            return Err(Error::InvalidShare);
        }
        if shares[1..].iter().any(|s| s.len() != shares[0].len()) {
            return Err(Error::InvalidShare);
        }
        Ok(())
    }
}

#[cfg(any(feature = "alloc", feature = "std"))]
fn lagrange_coefficients(shares: &[Vec<u8>]) -> VsssResult<Vec<IdentifierGf16>> {
    let identifiers: Vec<_> = shares
        .iter()
        .map(|share| IdentifierGf16(Gf16(share[0])))
        .collect();

    for identifier in &identifiers {
        if identifier.is_zero().into() {
            return Err(Error::SharingInvalidIdentifier);
        }
    }
    for (i, x_i) in identifiers.iter().enumerate() {
        for x_j in identifiers.iter().skip(i + 1) {
            if x_i == x_j {
                return Err(Error::SharingDuplicateIdentifier);
            }
        }
    }

    let mut coefficients = Vec::with_capacity(identifiers.len());
    for (i, x_i) in identifiers.iter().enumerate() {
        let mut num = IdentifierGf16::one();
        let mut den = IdentifierGf16::one();
        for (j, x_j) in identifiers.iter().enumerate() {
            if i == j {
                continue;
            }

            let d = *x_j.as_ref() - *x_i.as_ref();
            *den.as_mut() *= d;
            *num.as_mut() *= x_j.as_ref();
        }

        let den = den
            .invert()
            .map_err(|_| Error::SharingDuplicateIdentifier)?;
        coefficients.push((*num.as_ref() * den.as_ref()).into());
    }

    Ok(coefficients)
}

/// Constant-time multiplication in GF(2^4) modulo x^4 + x + 1.
///
/// Uses the i8 arithmetic trick for constant-time operation:
/// `-(b & 1)` in signed arithmetic gives 0 (b even) or -1/0xFF (b odd),
/// serving as a branchless conditional mask.
/// Reduction: when bit 3 overflows on left-shift, XOR with 0x03 (= x + 1,
/// the non-leading terms of the irreducible polynomial x^4 + x + 1).
fn gf16_mul(a: u8, b: u8) -> u8 {
    let mut a = (a & 0x0f) as i8;
    let mut b = (b & 0x0f) as i8;
    let mut r = 0i8;
    for _ in 0..4 {
        // If the LSB of b is 1, XOR a into the accumulator (constant-time via -(b&1)).
        r ^= a & -(b & 1);
        b >>= 1;
        // Extract bit 3 of a (the overflow bit after a left-shift).
        let hi = (a as u8 >> 3) as i8 & 1;
        // Create an all-ones mask if bit 3 was set, zero otherwise.
        let t = -hi;
        // Shift a left by 1, masking to 4 bits.
        a = (a << 1) & 0x0f;
        // If bit 3 was set, reduce by XOR with x+1 = 0x03 (the non-leading
        // terms of the irreducible polynomial x^4 + x + 1).
        a ^= 0x03i8 & t;
    }
    (r & 0x0f) as u8
}

/// Constant-time exponentiation in GF(2^4).
///
/// Computes `base^exp` using the left-to-right binary (MSB-first) square-and-multiply
/// method, processing the 4 significant bits of the exponent.
fn gf16_pow(base: u8, exp: u8) -> u8 {
    let mut result = 1u8;
    let base = base & 0x0f;
    // Process bits from MSB (bit 3) down to LSB (bit 0).
    for i in (0..4).rev() {
        result = gf16_mul(result, result);
        let tmp = gf16_mul(result, base);
        let allow = ((exp >> i) & 1).ct_eq(&1);
        result.conditional_assign(&tmp, allow);
    }
    result.conditional_assign(&1u8, exp.ct_eq(&0));
    result
}

#[derive(Debug, Copy, Clone, Default, Eq, PartialEq, Ord, PartialOrd, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(transparent)]
/// Represents an identifier in the Galois Field GF(2^4).
///
/// Used solely for Sequential Participant ID generation,
/// since GF16 addition = xor i.e. identifiers just oscillate between
/// the start number and the incremented number instead of adding.
pub struct IdentifierGf16(pub Gf16);

impl Display for IdentifierGf16 {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

#[cfg(feature = "zeroize")]
impl DefaultIsZeroes for IdentifierGf16 {}

impl Deref for IdentifierGf16 {
    type Target = Gf16;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl DerefMut for IdentifierGf16 {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl AsRef<Gf16> for IdentifierGf16 {
    fn as_ref(&self) -> &Gf16 {
        &self.0
    }
}

impl AsMut<Gf16> for IdentifierGf16 {
    fn as_mut(&mut self) -> &mut Gf16 {
        &mut self.0
    }
}

impl From<Gf16> for IdentifierGf16 {
    fn from(val: Gf16) -> Self {
        IdentifierGf16(val)
    }
}

impl From<&IdentifierGf16> for IdentifierGf16 {
    fn from(val: &IdentifierGf16) -> Self {
        IdentifierGf16(val.0)
    }
}

impl Mul<&IdentifierGf16> for IdentifierGf16 {
    type Output = IdentifierGf16;

    fn mul(self, rhs: &IdentifierGf16) -> IdentifierGf16 {
        IdentifierGf16(self.0 * rhs.0)
    }
}

impl ShareElement for IdentifierGf16 {
    type Serialization = [u8; 1];

    type Inner = Gf16;

    fn random(mut rng: impl CryptoRng) -> Self {
        // x-coordinate of a Shamir evaluation point; zero is reserved
        // for the secret (f(0)), so MUST be non-zero. Uniform over 1..=15.
        Self(Gf16(uniform_nonzero_u8(rng.next_u32(), 15)))
    }

    fn zero() -> Self {
        Self(Gf16::ZERO)
    }

    fn one() -> Self {
        Self(Gf16::ONE)
    }

    fn is_zero(&self) -> Choice {
        self.0.is_zero()
    }

    fn serialize(&self) -> Self::Serialization {
        [self.0.0]
    }

    fn deserialize(serialized: &Self::Serialization) -> VsssResult<Self> {
        Ok(Self(Gf16(serialized[0])))
    }

    fn from_slice(slice: &[u8]) -> VsssResult<Self> {
        if slice.len() != 1 {
            return Err(Error::InvalidShareElement);
        }
        Ok(Self(Gf16(slice[0])))
    }

    #[cfg(any(feature = "alloc", feature = "std"))]
    fn to_vec(&self) -> Vec<u8> {
        vec![self.0.0]
    }
}

impl ShareIdentifier for IdentifierGf16 {
    fn inc(&mut self, increment: &Self) {
        // Zero-on-overflow keyed to the GF(16) range (audit finding #3).
        // Prior `saturating_add` pinned at 15 (duplicates) and on larger
        // increments saturated to 255 — outside GF(16). See
        // `field_bounded_add` for the branch-free mask + halt-marker
        // contract shared with `IdentifierGf256::inc`.
        self.0.0 = field_bounded_add(self.0.0, increment.0.0, 16);
    }

    fn invert(&self) -> VsssResult<Self> {
        Option::from(self.0.invert())
            .map(Self)
            .ok_or(Error::InvalidShareElement)
    }

    fn random_coefficient(mut rng: impl CryptoRng) -> Self {
        // Bypass the "+1" non-zero x-sampler in `ShareElement::random`
        // and draw directly from `Gf16` — uniform over 0..=15.
        Self(Gf16::random(&mut rng))
    }
}

impl IdentifierGf16 {
    /// Returns additive identity.
    pub const ZERO: Self = Self(Gf16(0));
    /// Returns multiplicative identity.
    pub const ONE: Self = Self(Gf16(1));
}

#[cfg(test)]
#[cfg(any(feature = "alloc", feature = "std"))]
mod tests {
    use super::gf16_cmp;
    use super::*;
    use crate::shamir;
    use crate::{ParticipantIdGenerator, ParticipantIdGeneratorCollection};
    use rand::{RngExt, SeedableRng};
    use rand_chacha::ChaCha8Rng;
    use std::collections::HashSet;
    use std::prelude::v1::Vec;

    #[test]
    fn compatibility() {
        let mut rng = ChaCha8Rng::from_seed([57u8; 32]);
        for _ in 0..1000 {
            let a = rng.random::<u8>() & 0x0f;
            let b = rng.random::<u8>() & 0x0f;
            let y = Gf16(a);
            let z = Gf16(b);

            assert_eq!((y * z).0, gf16_cmp::gf16_mul(a, b));
        }
        rng = ChaCha8Rng::from_seed([99u8; 32]);
        for _ in 0..1000 {
            let a = rng.random::<u8>() & 0x0f;
            let b = rng.random::<u8>() & 0x0f;
            let y = Gf16(a);
            let z = Gf16(b);

            assert_eq!((y * z).0, gf16_cmp::gf16_mul(a, b));
        }

        // Verify all 15*15 = 225 non-zero products exhaustively
        for a in 1u8..=15 {
            for b in 1u8..=15 {
                assert_eq!(
                    gf16_mul(a, b),
                    gf16_cmp::gf16_mul(a, b),
                    "gf16_mul({a}, {b}) mismatch"
                );
            }
        }

        let mut rng = ChaCha8Rng::from_seed([57u8; 32]);
        for _ in 0..15 {
            let mut a = rng.random::<u8>() & 0x0f;
            while a == 0 {
                a = rng.random::<u8>() & 0x0f;
            }
            let y = Gf16(a);

            assert_eq!(y.invert().unwrap().0, gf16_cmp::gf16_inv(a));
        }
    }

    #[test]
    fn known_values() {
        // Powers of 2 (= x) in GF(2^4) with poly x^4+x+1:
        // x^1=2, x^2=4, x^3=8, x^4=3, x^5=6, x^6=12, x^7=11,
        // x^8=5, x^9=10, x^10=7, x^11=14, x^12=15, x^13=13, x^14=9, x^15=1
        let powers: [u8; 15] = [2, 4, 8, 3, 6, 12, 11, 5, 10, 7, 14, 15, 13, 9, 1];
        let mut val = Gf16(1);
        let generator = Gf16(2);
        for &expected in &powers {
            val *= generator;
            assert_eq!(val.0, expected);
        }

        // 2^(-1) = 9
        assert_eq!(Gf16(2).invert().unwrap().0, 9);
        // 3^(-1): 3 = x^4, so 3^(-1) = 2^(-4) = 2^11 = 14
        assert_eq!(Gf16(3).invert().unwrap().0, 14);
        // 1^(-1) = 1
        assert_eq!(Gf16(1).invert().unwrap().0, 1);
        // 0 has no inverse
        assert!(bool::from(Gf16(0).invert().is_none()));
    }

    #[test]
    fn shamir() {
        let mut rng = ChaCha8Rng::from_seed([57u8; 32]);
        for i in 1u8..=15 {
            let secret = IdentifierGf16(Gf16(i));
            let shares = shamir::split_secret::<GfShare>(3, 5, &secret, &mut rng).unwrap();
            assert_eq!(shares[0].identifier.0.0, 1);
            assert_eq!(shares[1].identifier.0.0, 2);
            assert_eq!(shares[2].identifier.0.0, 3);
            assert_eq!(shares[3].identifier.0.0, 4);
            assert_eq!(shares[4].identifier.0.0, 5);
            let res = &shares[0..3].to_vec().combine();
            assert!(
                res.is_ok(),
                "Failed at iteration {}, secret: {}",
                i,
                secret.0.0
            );
            assert_eq!(
                res.unwrap(),
                secret,
                "Failed at iteration {}, secret: {}",
                i,
                secret.0.0
            );
        }
        rng = ChaCha8Rng::from_seed([99u8; 32]);
        for i in 1u8..=15 {
            let secret = IdentifierGf16(Gf16(i));
            let shares = shamir::split_secret::<GfShare>(3, 5, &secret, &mut rng).unwrap();
            assert_eq!(shares[0].identifier.0.0, 1);
            assert_eq!(shares[1].identifier.0.0, 2);
            assert_eq!(shares[2].identifier.0.0, 3);
            assert_eq!(shares[3].identifier.0.0, 4);
            assert_eq!(shares[4].identifier.0.0, 5);
            let res = &shares[2..].to_vec().combine();
            assert_eq!(res.unwrap(), secret);
        }
    }

    #[test]
    fn split_array() {
        let mut rng = ChaCha8Rng::from_seed([57u8; 32]);
        let secret = b"Hello World!";
        let shares = Gf16::split_array(3, 5, secret, &mut rng).unwrap();
        assert_eq!(shares.len(), 5);

        let res = Gf16::combine_array(&shares[..3]);
        assert_eq!(res.unwrap(), secret);

        let shares = Gf16::split_bytes(3, 5, secret, &mut rng).unwrap();
        assert_eq!(shares.len(), 5);

        let res = Gf16::combine_bytes(&shares[..3]);
        assert_eq!(res.unwrap(), secret);

        let p = ParticipantIdGenerator::Sequential {
            start: IdentifierGf16(Gf16(1)),
            increment: IdentifierGf16(Gf16(1)),
            count: 5,
        };
        let shares =
            Gf16::split_array_with_participant_generators(3, 5, secret, &mut rng, &[p]).unwrap();
        assert_eq!(shares.len(), 5);

        let res = Gf16::combine_array(&shares[..3]);
        let secret2 = res.unwrap();
        assert_eq!(secret2, secret);

        let ids = (1u8..=5).map(|id| IdentifierGf16(Gf16(id)));
        let shares =
            Gf16::split_bytes_with_participant_ids_iter(3, 5, secret, &mut rng, ids).unwrap();
        assert_eq!(shares.len(), 5);

        let res = Gf16::combine_bytes(&shares[..3]);
        let secret2 = res.unwrap();
        assert_eq!(secret2, secret);

        let res = Gf16::combine_array(&[shares[4].clone(), shares[1].clone(), shares[3].clone()]);
        let secret2 = res.unwrap();
        assert_eq!(secret2, secret);
    }

    #[cfg(feature = "stream")]
    #[test]
    fn split_and_combine_byte_streams() {
        use crate::tests::utils::{TestStream, block_on};

        let mut rng = ChaCha8Rng::from_seed([58u8; 32]);
        let secret = b"streamed secret";
        let ids = (1u8..=5).map(|id| IdentifierGf16(Gf16(id)));
        let shares = block_on(Gf16::split_bytes_with_participant_ids_stream(
            3,
            5,
            secret,
            &mut rng,
            TestStream::new(ids),
        ))
        .unwrap();

        assert_eq!(
            Gf16::combine_bytes_iter(shares[..3].iter().cloned()).unwrap(),
            secret
        );
        let stream = TestStream::new(shares[..3].iter().cloned());
        assert_eq!(
            block_on(Gf16::combine_bytes_stream(3, stream)).unwrap(),
            secret
        );

        let stream = TestStream::new(shares[..2].iter().cloned());
        assert_eq!(
            block_on(Gf16::combine_bytes_stream(3, stream)),
            Err(Error::NotEnoughShares)
        );
    }

    #[test]
    fn combine_fuzz() {
        let res = Gf16::combine_array(&[vec![], vec![]]);
        assert!(res.is_err());
        let res = Gf16::combine_array(&[vec![1u8, 8u8], vec![2u8]]);
        assert!(res.is_err());

        let mut rng = ChaCha8Rng::from_seed([99u8; 32]);
        for _ in 0..25 {
            let threshold = (rng.random::<u8>() & 0x0f).saturating_add(1);

            let mut shares = Vec::with_capacity(threshold as usize);
            for i in 0..threshold {
                let share = vec![i; (rng.random::<u8>() as usize % 16) + 1];
                shares.push(share);
            }
            assert!(Gf16::combine_array(shares).is_err());
        }
    }

    /// Audit finding #1 (GF(16) analogue): `Gf16::random` must be
    /// uniform over the entire field, including even nibbles. The
    /// prior `(b & 0x0E) + 1` only produced odd values 1, 3, ..., 15.
    #[test]
    fn poc1_biased_gf16() {
        // 128 draws comfortably exceeds the ~10 needed to see even and
        // zero under a uniform distribution over 16 values.
        let mut rng = ChaCha8Rng::from_seed([57u8; 32]);
        let mut seen_even = false;
        let mut seen_zero = false;
        for _ in 0..128 {
            let x = <Gf16 as Field>::random(&mut rng).0;
            assert!(x < 16, "Gf16::random out of range: {x}");
            if x % 2 == 0 {
                seen_even = true;
            }
            if x == 0 {
                seen_zero = true;
            }
        }
        assert!(
            seen_even,
            "Gf16::random produced no even values — bias regression"
        );
        assert!(
            seen_zero,
            "Gf16::random produced no zero values over 10k draws"
        );
    }

    /// Audit finding #1 (GF(16) analogue): x-identifier must be
    /// non-zero and within the field range.
    #[test]
    fn poc1_identifier_gf16_nonzero() {
        // 1024 draws is sufficient to catch any biased sampler that can
        // produce zero or out-of-range values.
        let mut rng = ChaCha8Rng::from_seed([0xA5u8; 32]);
        for _ in 0..1024 {
            let id = IdentifierGf16::random(&mut rng);
            assert_ne!(id.0.0, 0, "IdentifierGf16::random yielded zero");
            assert!(
                id.0.0 < 16,
                "IdentifierGf16::random out of range: {}",
                id.0.0
            );
        }
    }

    /// Audit finding #3 (GF(16) analogue): sequential identifier
    /// generation must halt cleanly at 15 instead of saturating to
    /// an out-of-field value or pinning at 15.
    #[test]
    fn poc3_gf16_inc_bounds_check() {
        // Start near the upper boundary. Old saturating code would
        // pin at 15 (or leak values outside GF(16) with larger
        // increments); new code halts the stream after 15.
        let start = IdentifierGf16(Gf16(13));
        let inc = IdentifierGf16(Gf16(1));
        let seq = ParticipantIdGenerator::Sequential {
            start,
            increment: inc,
            count: 10,
        };
        let generators = [seq];
        let collection = ParticipantIdGeneratorCollection::from(&generators[..]);
        let ids: Vec<_> = collection.iter().collect();

        let mut seen = HashSet::new();
        for id in &ids {
            assert!(
                seen.insert(id.0.0),
                "duplicate identifier emitted: {}",
                id.0.0
            );
            assert!(
                id.0.0 > 0 && id.0.0 < 16,
                "id out of GF(16) range: {}",
                id.0.0
            );
        }
        assert!(
            ids.len() <= 3,
            "generator emitted {} ids past GF(16) boundary — saturating_add regression",
            ids.len()
        );
    }

    /// Direct observation of audit finding #2 over GF(16): polynomial
    /// `fill` must produce zero coefficients. With only 16 field
    /// elements, P(zero)=1/16 per coefficient — zeros should appear
    /// frequently across runs.
    #[test]
    fn zero_coefficients_actually_occur() {
        use crate::Polynomial;
        let mut rng = ChaCha8Rng::from_seed([0x7Fu8; 32]);
        let intercept = IdentifierGf16(Gf16(0x05));
        let threshold = 8usize;
        let runs = 50;
        let mut zero_coef_count = 0usize;
        for _ in 0..runs {
            let mut poly: Vec<GfShare> = <Vec<GfShare> as Polynomial<GfShare>>::create(threshold);
            poly.fill(&intercept, &mut rng, threshold).unwrap();
            for coef in &poly[1..threshold] {
                if coef.identifier.0.0 == 0 {
                    zero_coef_count += 1;
                }
            }
        }
        // 50 runs × 7 coefficients = 350 draws; under uniform GF(16)
        // expected zeros ≈ 350/16 ≈ 21. Prior biased fill yields 0.
        assert!(
            zero_coef_count > 0,
            "No zero coefficient across {runs} fills × {} slots — coefficient sampling still biased against zero",
            threshold - 1,
        );
    }

    /// A zero secret over GF(16) must split and reconstruct correctly.
    /// The existing `shamir` test iterates secrets 1..=15 only.
    #[test]
    fn zero_secret_round_trip() {
        let mut rng = ChaCha8Rng::from_seed([0xC3u8; 32]);
        let zero_secret = IdentifierGf16(Gf16(0));
        let shares = shamir::split_secret::<GfShare>(3, 5, &zero_secret, &mut rng).unwrap();
        let recovered = shares[..3].to_vec().combine().unwrap();
        assert_eq!(recovered, zero_secret, "zero-secret round-trip failed");
        let recovered2 = shares[2..].to_vec().combine().unwrap();
        assert_eq!(recovered2, zero_secret);
    }

    /// Shares whose nibble values are zero must still round-trip via
    /// `split_array`/`combine_array`. Over GF(16) with many reps, zero
    /// nibbles are extremely common.
    #[test]
    fn zero_valued_shares_round_trip() {
        let mut rng = ChaCha8Rng::from_seed([0x5Au8; 32]);
        let secret = b"The quick brown fox jumps over the lazy dog";
        let runs = 20;
        let mut saw_zero_nibble = false;
        for _ in 0..runs {
            let shares = Gf16::split_array(5, 8, secret, &mut rng).unwrap();
            for s in &shares {
                for &b in &s[1..] {
                    if (b & 0x0F) == 0 || (b >> 4) == 0 {
                        saw_zero_nibble = true;
                    }
                }
            }
            let recovered = Gf16::combine_array(&shares[..5]).unwrap();
            assert_eq!(
                &recovered[..],
                secret,
                "combine failed over GF(16) with zero-valued nibbles"
            );
        }
        assert!(
            saw_zero_nibble,
            "No zero nibble observed — statistical regression"
        );
    }

    /// Every share identifier emitted by GF(16) `split_secret` is
    /// non-zero (zero reserved for f(0) = secret).
    #[test]
    fn no_share_identifier_is_zero() {
        let mut rng = ChaCha8Rng::from_seed([0xDEu8; 32]);
        for _ in 0..50 {
            let secret = IdentifierGf16(Gf16(rng.random::<u8>() & 0x0F));
            let shares = shamir::split_secret::<GfShare>(3, 5, &secret, &mut rng).unwrap();
            for s in &shares {
                assert_ne!(
                    s.identifier.0.0, 0,
                    "zero identifier produced by GF(16) split_secret",
                );
            }
        }
    }

    #[test]
    fn gf16_formatting_conversions_and_field_methods_work() {
        use elliptic_curve::ff::{Field, PrimeField};
        use std::{format, string::ToString};
        use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};

        let value = Gf16(0x0a);
        assert_eq!(value.to_string(), "10");
        assert_eq!(format!("{value:x}"), "a");
        assert_eq!(format!("{value:X}"), "A");
        assert_eq!(format!("{value:b}"), "1010");
        assert_eq!(
            Gf16::conditional_select(&Gf16(1), &Gf16(2), Choice::from(1)),
            Gf16(2)
        );
        assert_eq!(Gf16(7).ct_eq(&Gf16(7)).unwrap_u8(), 1);

        assert_eq!(u8::from(Gf16::from(0x12u8)), 0x12);
        assert_eq!(u16::from(Gf16::from(0x12u16)), 0x12);
        assert_eq!(u32::from(Gf16::from(0x12u32)), 0x12);
        assert_eq!(u64::from(Gf16::from(0x12u64)), 0x12);
        assert_eq!(u128::from(Gf16::from(0x12u128)), 0x12);

        assert_eq!(Gf16::from_repr([0x0b]).unwrap(), Gf16(0x0b));
        assert_eq!(Gf16(0x0b).to_repr(), [0x0b]);
        assert_eq!(Gf16(3).is_odd().unwrap_u8(), 1);
        assert_eq!(Gf16(2).is_odd().unwrap_u8(), 0);
        assert_eq!(Gf16(3).square(), Gf16(3) * Gf16(3));
        assert_eq!(Gf16(3).double(), Gf16(0));
        assert_eq!(Gf16(3).invert().unwrap() * Gf16(3), Gf16(1));
        assert!(bool::from(Gf16(0).invert().is_none()));
        assert_eq!(Gf16(2).pow(3), Gf16(8));
        let (_, sqrt) = Gf16::sqrt_ratio(&Gf16(1), &Gf16(1));
        assert_eq!(sqrt.square(), sqrt);
    }

    #[test]
    fn gf16_operator_reference_forms_assignments_sum_and_product_work() {
        use core::ops::{Add, BitAnd, BitOr, BitXor, Div, Mul, Neg, Sub};

        let a = Gf16(0x03);
        let b = Gf16(0x05);
        assert_eq!(a + b, Gf16(0x06));
        assert_eq!(<Gf16 as Add<&Gf16>>::add(a, &b), Gf16(0x06));
        assert_eq!(<&Gf16 as Add<Gf16>>::add(&a, b), Gf16(0x06));
        assert_eq!(<&Gf16 as Add<&Gf16>>::add(&a, &b), Gf16(0x06));
        assert_eq!(a - b, Gf16(0x06));
        assert_eq!(<Gf16 as Sub<&Gf16>>::sub(a, &b), Gf16(0x06));
        assert_eq!(<&Gf16 as Sub<Gf16>>::sub(&a, b), Gf16(0x06));
        assert_eq!(<&Gf16 as Sub<&Gf16>>::sub(&a, &b), Gf16(0x06));
        assert_eq!(a * b, Gf16(gf16_mul(3, 5)));
        assert_eq!(<Gf16 as Mul<&Gf16>>::mul(a, &b), a * b);
        assert_eq!(<&Gf16 as Mul<Gf16>>::mul(&a, b), a * b);
        assert_eq!(<&Gf16 as Mul<&Gf16>>::mul(&a, &b), a * b);
        assert_eq!(a / b, a * b.invert().unwrap());
        assert_eq!(<Gf16 as Div<&Gf16>>::div(a, &b), a / b);
        assert_eq!(<&Gf16 as Div<Gf16>>::div(&a, b), a / b);
        assert_eq!(<&Gf16 as Div<&Gf16>>::div(&a, &b), a / b);
        assert_eq!(Neg::neg(a), a);
        assert_eq!(a & b, Gf16(0x01));
        assert_eq!(<Gf16 as BitAnd<&Gf16>>::bitand(a, &b), Gf16(0x01));
        assert_eq!(<&Gf16 as BitAnd<Gf16>>::bitand(&a, b), Gf16(0x01));
        assert_eq!(<&Gf16 as BitAnd<&Gf16>>::bitand(&a, &b), Gf16(0x01));
        assert_eq!(a | b, Gf16(0x07));
        assert_eq!(<Gf16 as BitOr<&Gf16>>::bitor(a, &b), Gf16(0x07));
        assert_eq!(<&Gf16 as BitOr<Gf16>>::bitor(&a, b), Gf16(0x07));
        assert_eq!(<&Gf16 as BitOr<&Gf16>>::bitor(&a, &b), Gf16(0x07));
        assert_eq!(a ^ b, Gf16(0x06));
        assert_eq!(<Gf16 as BitXor<&Gf16>>::bitxor(a, &b), Gf16(0x06));
        assert_eq!(<&Gf16 as BitXor<Gf16>>::bitxor(&a, b), Gf16(0x06));
        assert_eq!(<&Gf16 as BitXor<&Gf16>>::bitxor(&a, &b), Gf16(0x06));

        let mut assigned = a;
        assigned += b;
        assert_eq!(assigned, Gf16(0x06));
        assigned -= &b;
        assert_eq!(assigned, a);
        assigned *= b;
        assert_eq!(assigned, a * b);
        assigned /= &b;
        assert_eq!(assigned, a);
        assigned &= b;
        assert_eq!(assigned, Gf16(0x01));
        assigned |= &Gf16(0x08);
        assert_eq!(assigned, Gf16(0x09));
        assigned ^= b;
        assert_eq!(assigned, Gf16(0x0c));

        assert_eq!([Gf16(1), Gf16(2), Gf16(3)].iter().sum::<Gf16>(), Gf16(0));
        assert_eq!([Gf16(2), Gf16(3)].iter().product::<Gf16>(), Gf16(6));
    }

    #[test]
    fn gf16_identifier_share_element_and_error_paths_work() {
        let identifier = IdentifierGf16(Gf16(7));
        assert_eq!(IdentifierGf16::from(Gf16(7)), identifier);
        assert_eq!(IdentifierGf16::from(&identifier), identifier);
        assert_eq!(identifier.serialize(), [7]);
        assert_eq!(IdentifierGf16::deserialize(&[7]), Ok(identifier));
        assert_eq!(IdentifierGf16::from_slice(&[7]), Ok(identifier));
        assert_eq!(
            IdentifierGf16::from_slice(&[1, 2]),
            Err(Error::InvalidShareElement)
        );
        assert_eq!(identifier.to_vec(), vec![7]);
        assert_eq!(IdentifierGf16::zero().is_zero().unwrap_u8(), 1);
        assert_eq!(IdentifierGf16::one().is_zero().unwrap_u8(), 0);
        assert_eq!(IdentifierGf16::one().invert(), Ok(IdentifierGf16::one()));
        assert_eq!(
            IdentifierGf16::zero().invert(),
            Err(Error::InvalidShareElement)
        );

        let mut incremented = IdentifierGf16(Gf16(14));
        incremented.inc(&IdentifierGf16(Gf16(1)));
        assert_eq!(incremented, IdentifierGf16(Gf16(15)));
        incremented.inc(&IdentifierGf16(Gf16(1)));
        assert_eq!(incremented, IdentifierGf16(Gf16(0)));

        assert_eq!(
            Gf16::combine_array(Vec::<Vec<u8>>::new()),
            Err(Error::SharingMinThreshold)
        );
        assert_eq!(
            Gf16::combine_array(vec![vec![1]]),
            Err(Error::SharingMinThreshold)
        );
        assert_eq!(
            Gf16::combine_array(vec![vec![1], vec![2, 3]]),
            Err(Error::InvalidShare)
        );
        assert_eq!(
            Gf16::combine_array(vec![vec![0, 1], vec![2, 3]]),
            Err(Error::SharingInvalidIdentifier)
        );
        assert_eq!(
            Gf16::combine_array(vec![vec![1, 1], vec![1, 3]]),
            Err(Error::SharingDuplicateIdentifier)
        );
        let mut rng = ChaCha8Rng::from_seed([0x22u8; 32]);
        assert_eq!(
            Gf16::split_array(2, 16, b"x", &mut rng),
            Err(Error::InvalidSizeRequest)
        );
        assert_eq!(
            Gf16::split_array(2, 2, b"", &mut rng),
            Err(Error::InvalidSecret)
        );
        assert_eq!(
            Gf16::split_bytes_with_participant_ids_iter(
                2,
                2,
                b"x",
                &mut rng,
                [IdentifierGf16(Gf16(0)), IdentifierGf16(Gf16(1))]
            ),
            Err(Error::SharingInvalidIdentifier)
        );
    }
}

#[cfg(test)]
#[cfg(any(feature = "alloc", feature = "std"))]
mod gf16_cmp {
    // Reference implementation using carryless multiplication with explicit reduction.
    // Based on: https://github.com/mikelodder7/mayo/blob/main/src/gf16.rs
    // Irreducible polynomial: x^4 + x + 1.
    // Reduction rule: x^4 = x + 1, x^5 = x^2 + x, x^6 = x^3 + x^2.
    // For the degree-6 product of two degree-3 polynomials, high nibble bits 4-6
    // each reduce to two lower-bit contributions:
    //   bit 4 -> bits 0,1 (x^4 = x+1)
    //   bit 5 -> bits 1,2 (x^5 = x^2+x)
    //   bit 6 -> bits 2,3 (x^6 = x^3+x^2)
    // So: result = (low nibble) ^ (high_nibble >> 4) ^ (high_nibble >> 3).

    /// Multiply two GF(16) elements mod x^4 + x + 1.
    pub fn gf16_mul(a: u8, b: u8) -> u8 {
        let mut p: u8 = 0;
        p ^= (a & 1).wrapping_mul(b);
        p ^= (a & 2).wrapping_mul(b);
        p ^= (a & 4).wrapping_mul(b);
        p ^= (a & 8).wrapping_mul(b);
        let top_p = p & 0xf0;
        (p ^ (top_p >> 4) ^ (top_p >> 3)) & 0x0f
    }

    /// Compute a^(-1) in GF(16) via a^14 = a^8 * a^4 * a^2.
    pub fn gf16_inv(a: u8) -> u8 {
        let a2 = gf16_mul(a, a);
        let a4 = gf16_mul(a2, a2);
        let a8 = gf16_mul(a4, a4);
        let a6 = gf16_mul(a2, a4);
        gf16_mul(a8, a6)
    }
}