pluto / ronkathon

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

feat: Modular Arithmetic Optimization #16

Closed 0xJepsen closed 6 months ago

0xJepsen commented 6 months ago

I think there are two modular arithmetic optimizations that would be good to add to the field.rs component.

While they each have there distinct applications and performance improvements, since this is a learning resource, i believe we should at some point add both of them and well document each.

There is a pretty good resource on both these algorithms with slides from risc0 here

0xJepsen commented 6 months ago

@lonerapier Would this be something you are interested in?

lonerapier commented 6 months ago

Yup @0xJepsen, will start on this

0xJepsen commented 6 months ago

Yup @0xJepsen, will start on this

There is an example of the montgomery optimization here: https://github.com/Plonky3/Plonky3/blob/main/baby-bear/src/baby_bear.rs, it does depend on the field size.