perf: fast polynomial multiplication and division in lagrange domain.

[0xJepsen]

[Autoparallel]

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

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

[lonerapier]

@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.

[Autoparallel]

Needs more info

[mahmudsudo]

can i take on this ?

[Autoparallel]

Sure!

Keep in mind Horner's method.

Basically, we just use the convolution theorem