Function lagrange_evals

pub fn lagrange_evals<F: BinaryField>(
    subspace: &BinarySubspace<F>,
    z: F,
) -> Vec<F>

Optimized Lagrange evaluation for power-of-2 domains in binary fields.

Computes the Lagrange polynomial evaluations L̃(z, i) for a power-of-2 domain at point z. Uses the provided binary subspace as the evaluation domain.

Key Optimization

For power-of-2 domains, all barycentric weights are identical due to the additive group structure. For each i ∈ {0, …, 2^k - 1}, the set {i ⊕ j | j ≠ i} = {1, …, 2^k - 1}. This allows us to:

1. Compute a single barycentric weight w = 1 / ∏_{j=1}^{n-1} j
2. Use prefix/suffix products to avoid redundant computation
3. Replace inversions with multiplications for better performance

Complexity

• Time: O(n) where n = subspace size, using 4n - 2 multiplications and 1 inversion
• Space: O(n) for prefix/suffix arrays

Parameters

• subspace: The binary subspace defining the evaluation domain
• z: The evaluation point

Returns

A vector of Lagrange polynomial evaluations, one for each domain element