The problem Irreducible: Additive NTT solves

The problem aims to optimize the current version of NTT in Binius.

The submitted version tried to mimic the STWO implementation. We did not get this running correctly, but believe that this approach might bring a performance benefit. Our implementation is failing test_repetition_property. With the submitted version, we achieved 62.031% time improvement on x86 architecture.

Challenges we ran into

Implementing Precomputation of the Gao–Mateer Basis in Rust
The existing Python code relies on deeply nested, generic types. Recasting these abstractions in Rust requires designing appropriate structs and traits

Correct Ordering in Twiddle-Factor Generation for the Gao–Mateer Basis
Develop an algorithm to generate and sequence twiddle factors across multiple basis layers. The current approach emits basis elements in ascending (smallest-first) order, which violates the mathematical requirements of the Gao–Mateer basis. The challenge is to derive the correct layer-by-layer ordering and implement it efficiently.

Debugging the ‘Repetition Property’ Test Failure
The implementation crashes under the repetition-property test due to an unsafe memory error. We would need to pinpoint and resolve the out-of-bounds or invalid-pointer access within our unsafe blocks.