FFT/NTT Optimization / Additional Development

[MauroToscano]

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