FFT on Goldilocks

[ThomasPiellard]

In order to make Vortex efficient, one has to implement an efficient FFT on Goldilocks (instead of the usual ~256bits field like the field of bn254 for instance) due to a wrong choice of security parameters (see https://eprint.iacr.org/2022/1754.pdf).

The FFTs will likely be of sizes ranging from 32 to 256. Typically we need to perform a lot of FFTs on a coset, where the inputs are in regular form (regular = non bit reversed), do some operations on the result (namely adding some vectors), and at the end perform one FFT inverse on a coset, where the input is bit reversed (in fact we don't need to perform any bit reverse).

The goal is to beat the current implementation, with the following benchmarks for the FFT on coset, without bit reverse gnark-crypto v0.9.0 PROC: 2.2GHz 6-core Intel core i7 MEM : 16GB 2400 MHz DDR4

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
BenchmarkFFT/[FFT_SIZE_32]-12             186336              6478 ns/op
BenchmarkFFT/[FFT_SIZE_64]-12              86384             13598 ns/op
BenchmarkFFT/[FFT_SIZE_128]-12             59871             19726 ns/op
BenchmarkFFT/[FFT_SIZE_256]-12             50614             23531 ns/op

[Ludcour]

Shall we close this one guys? It's been open for ages