Fastest NTT #1
Comments
|
With @Munksgaard's help and by using I have not yet managed to implement the algorithm from Microsoft Research linked above though. |
|
There is something called "bit-reversal" ordering in the Microsoft Research article that I don't know what means. |
|
Perhaps this is what they mean? https://en.wikipedia.org/wiki/Bit-reversal_permutation |
That makes sense as the input always has length 2^n so such a permutation should be possible. So we need to map the value at index |
This allows us to compare the previous N^2 implementation of Lagrange interpolation with the new NTT-based N*log(N) implementation. As expected, the N*log(N) runtime scales nearly linearly which is awesome. Our NTT implementation can still be made much more efficient though, as noted in issue #1.
This allows us to compare the previous N^2 implementation of Lagrange interpolation with the new NTT-based N*log(N) implementation. As expected, the N*log(N) runtime scales nearly linearly which is awesome. Our NTT implementation can still be made much more efficient though, as noted in issue #1.
|
Might be what is implemented here: https://github.com/dusk-network/plonk/blob/d3412cec5fa5c2e720f848a6fd8db96d663e92a9/src/fft/domain.rs#L310 |
|
Closed by 524f54e and associated commits. We should have a pretty fast implementation now and NTT is nowhere near being a bottle-neck for any of our STARKs (Rescue Prime, Brainfuck, or Triton VM), so there's no reason to dwell more on this I think. |
…tsongs-attack into master Reviewed-on: https://neptune.builders/core-team/twenty-first/pulls/1
This paper from Microsoft Research seems to contain a pseudo-algorithm for what is probably the optimal NTT implementation.
https://eprint.iacr.org/2016/504.pdf
Another article about a fast NTT:
https://crypto.ethz.ch/publications/files/Seiler18.pdf
The text was updated successfully, but these errors were encountered: