Function batch_invert

pub fn batch_invert<const N: usize>(
    elements: &mut [BinaryField128bGhash],
    scratchpad: &mut [BinaryField128bGhash],
)

Efficiently inverts multiple field elements simultaneously using Montgomery’s batch inversion trick.

This function implements a binary tree approach to batch field inversion, which is significantly more efficient than inverting each element individually when dealing with many elements.

Algorithm Overview

1. Product Tree Construction: Build a binary tree bottom-up where leaves are input elements and each internal node stores the product of its children using linear addressing
2. Root Inversion: Perform single expensive field inversion on the root (product of all elements)
3. Inverse Propagation: Propagate the root inverse down through tree levels to compute individual element inverses

Performance Benefits

• Single inversion: Only one expensive field inversion instead of N inversions
• Linear addressing: Simple addition-based indexing for better cache locality
• Zero handling: Graceful handling of zero elements without division-by-zero errors

Parameters

• elements: Array of field elements to invert (modified in-place)
• scratchpad: Working memory buffer, must be at least 2*N-1 elements

Requirements

• N must be a power of 2 and ≥ 2
• scratchpad.len() >= 2*N-1 for intermediate computations