Mixed radix FFT

[imeckler]

First of all, incredible work. This is an enormous contribution in the path toward making zk-SNARKs super practical. Now on to the issue :)

For one curves in Coda, we actually perform a "mixed-radix" FFT as opposed to a binary FFT. The idea is that for the field Fr, we have r - 1 = 2^n * 5^m * R, and so you can do larger FFTs (i.e., handle larger constraint systems) by decomposing into 5 sub-problems up to m times before decomposing into 2 sub-problems as in the binary FFT.

We have code for this here. Do you think it would be possible to support this in the CUDA implementation? Happy to help by contributing code etc.

By the way -- I sent you a message on LinkedIn, have a few things I'd love to talk about. If interested, feel free to mail me at [email protected]