search

pluto / ronkathon

Cryptography Educational Foundations
https://pluto.xyz/blog/ronkathon-learn-cryptography-from-first-principles
Apache License 2.0
187 stars 23 forks source link

fast polynomial multiplication and division in lagrange domain. #34

Open 0xJepsen opened 6 months ago

Autoparallel commented 6 months ago

This overlaps pretty heavily with FFT (division less so).

Can we refine this issue? It is a bit unclear at the moment.

lonerapier commented 6 months ago

@Autoparallel we can implement this now right? as we have DFT to change the basis. Multiplication and division in monomial basis takes O(n^2), while in lagrange basis, it's O(n). I understood it from these amazing stark anatomy blogs.

Plonkathon also has it implemented in it's polynomial module.