FFT/NTT Optimization / Additional Development

[MauroToscano]

trafficstars

FTT/NTT is a bottleneck for some provers, any improvement in this operations is really useful

• [ ] Bench against plonky2 architecture specific implementation of inplace bit reversal https://github.com/0xPolygonZero/plonky2/blob/a9060e61b8004525b6f84c69dd21ad1a5cd1c3b2/util/src/lib.rs#L110
• [ ] If benches show a speedup, upgrade the algorithm with Plonky2 tricks
• [ ] Add split radix FFT
• [ ] Add reverse to natural implementations.
• [ ] Add natural-natural
• [ ] Add reverse to reverse
• [ ] Rework the API so the Input Output order is selected with an enum, and the function stays the same
• [ ] Experiment with adding a Stockham FFT to remove the final bit-reverse permutation step and bench. Sources: Pikara Fast poly multiplication, Moreno-Maza