pluto / ronkathon

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

feat: coset division #36

Open 0xJepsen opened 6 months ago

kevaundray commented 4 months ago

IIUC -- coset division is useful for when the polynomial you are dividing by, vanishes on the domain. ie we want to compute f(x)/g(x) and we want to do it in lagrange basis.

If g(x) vanishes on the domain, then you will end up with a division by 0. Commonly with SNARKs, your domain are the 2^n'th roots of unity because you are doing an FFT and g(x) has roots on it because it is likely the vanishing polynomial x^n - 1 (does not need to be).

To mitigate this, you evaluate f(x) and g(x) on a coset of the roots of unity

Autoparallel commented 4 months ago

This is a good explanation from @kevaundray, thank you :)