lib.rs

#![no_std]
//! strata-compute — tier 3: computation traits.
//!
//! traits needed by nox (VM execution) and jali (ring arithmetic).
//! these represent computational capabilities beyond basic arithmetic.
//!
//! ## Spectral
//!
//! a field with roots of unity — the spectral domain exists.
//! polynomial evaluation at all N-th roots of unity simultaneously
//! (the NTT / number theoretic transform) runs in O(N log N) instead of O(N²).
//!
//! the name "spectral" comes from spectral methods in numerical analysis:
//! transform between coefficient domain and evaluation domain, compute in
//! whichever domain is cheaper, transform back.
//!
//! ## Packed
//!
//! N field elements in one SIMD-width value. arithmetic operates on all N
//! elements simultaneously. this is the single biggest performance lever
//! for NTT, polynomial evaluation, and constraint checking.
//!
//! plonky3's entire speed advantage comes from packed field operations.
//! the key insight: NTT butterflies, polynomial evaluations, and constraint
//! checks are all element-wise — they parallelize perfectly across SIMD lanes.
//!
//! ## Bits
//!
//! decompose field elements into bits and reconstruct from bits.
//! nox uses this for binary operations (comparison, shifts, masks).

use strata_core::Field;

/// a field with spectral structure: roots of unity and NTT.
///
/// the multiplicative group F* has a subgroup of order 2^S
/// generated by the 2^S-th root of unity. this enables the
/// number theoretic transform (NTT) for O(N log N) polynomial
/// evaluation and interpolation.
///
/// not all fields are spectral:
/// - Goldilocks: yes (S = 32, 2^32-th root of unity exists)
/// - F₂¹²⁸: no (multiplicative group has order 2^128 - 1, not smooth)
/// - F_q (CSIDH): no (q-1 chosen for isogeny structure, not NTT)
/// - Tropical: not a field
pub trait Spectral: Field {
    /// two-adicity: largest k such that 2^k divides |F*|.
    const TWO_ADICITY: u32;

    /// primitive 2^S-th root of unity.
    const ROOT_OF_UNITY: Self;

    /// inverse of the root of unity.
    const ROOT_OF_UNITY_INV: Self;

    /// multiplicative generator of F*.
    const GENERATOR: Self;

    /// get a root of unity of order n.
    /// n must be a power of 2 and n ≤ 2^TWO_ADICITY.
    fn root_of_unity(n: usize) -> Self {
        assert!(n.is_power_of_two());
        let log_n = n.trailing_zeros();
        assert!(log_n <= Self::TWO_ADICITY);
        let exp = 1u64 << (Self::TWO_ADICITY - log_n);
        Self::ROOT_OF_UNITY.pow(exp)
    }
}

/// N field elements packed into one SIMD-width value.
///
/// all arithmetic (add, sub, mul, neg) operates lane-wise on WIDTH elements
/// simultaneously. this is the primary performance abstraction — NTT butterflies,
/// polynomial evaluations, and constraint checks parallelize across lanes.
///
/// implementations:
/// - Goldilocks: WIDTH=4 (AVX2, 4×64-bit) or WIDTH=1 (scalar fallback)
/// - F₂: kuro's Packed128 already packs 128 elements per u128
/// - Fq: WIDTH=1 (512-bit elements don't benefit from SIMD packing)
///
/// the trait extends Field so packed values support all field operations.
/// the Scalar associated type is the unpacked element type.
pub trait Packed: Field {
    /// the unpacked scalar element type.
    type Scalar: Field;

    /// number of scalar elements per packed value.
    const WIDTH: usize;

    /// pack scalar elements from a slice.
    /// slice length must be exactly WIDTH.
    fn from_slice(slice: &[Self::Scalar]) -> Self;

    /// unpack scalar elements into a slice.
    /// slice length must be exactly WIDTH.
    fn to_slice(&self, slice: &mut [Self::Scalar]);

    /// broadcast one scalar to all lanes.
    fn broadcast(val: Self::Scalar) -> Self;

    /// extract the scalar at lane index.
    fn extract(&self, index: usize) -> Self::Scalar;

    /// interleave low halves of two packed values.
    /// given [a0,a1,a2,a3] and [b0,b1,b2,b3], returns [a0,b0,a1,b1].
    /// essential for NTT butterfly patterns.
    fn interleave_low(self, other: Self) -> Self;

    /// interleave high halves of two packed values.
    /// given [a0,a1,a2,a3] and [b0,b1,b2,b3], returns [a2,b2,a3,b3].
    fn interleave_high(self, other: Self) -> Self;
}

/// decompose field elements into bits and reconstruct.
///
/// nox uses bit decomposition for comparison (lt), shifts, masks.
/// Binius uses it for binary constraint encoding (1 constraint per bit).
pub trait Bits: Field {
    /// number of bits in the canonical representation.
    const NUM_BITS: u32;

    /// decompose into little-endian bits.
    fn to_bits_le(&self) -> alloc::vec::Vec<bool>;

    /// reconstruct from little-endian bits.
    fn from_bits_le(bits: &[bool]) -> Self;
}

extern crate alloc;