search

indutny / fft.js

The fastest JS Radix-4/Radix-2 FFT implementation
278 stars 31 forks source link

number-theoretic transform? #12

Closed benediamond closed 5 years ago

benediamond commented 5 years ago

hey @indutny,

incredible work as always.

I'm wondering if you've considered implementing the number-theoretic transform---i.e. the FFT in a prime field F_q which admits high-order 2-adic roots of unity. There's also a version where the input "signal" is a vector of points on an elliptic curve E(F_p) of order q.

For example, consider the elliptic curve altbn_128, used in Ethereum precompiles---see here for an implementation built off your elliptic package. See herumi / ate-pairing for more details (it's called "CurveSNARK" there).

The order q of this curve is such that the field F_q admits 2^n-order modular-multiplicative roots of unity for n as high as 28. Thus one can take FFTs of power-of-2-length vectors consisting either of elements of F_q or of curve points.

Of course this isn't hard to implement manually but I'd enjoy your optimizations. Also happy to contribute if you'd be interested in going this direction.

indutny commented 5 years ago

Hello!

Thank you for kind words.

I have not considered implementing FFT over a field, as I never had a use of it.

Sorry!