keep-starknet-strange / garaga

State-of-the-art Elliptic Curve operations and SNARKS verification for Cairo & Starknet 🐺.

MIT License

170 stars 37 forks source link

Residue witness #122

Closed shramee closed 1 month ago

shramee commented 2 months ago

Implements finding a residue witness to avoid final exponentiation as described in https://ia.cr/2024/640

Pull Request type

Please check the type of change your PR introduces:

[ ] Bugfix
[x] Feature
[ ] Code style update (formatting, renaming)
[ ] Refactoring (no functional changes, no API changes)
[ ] Build-related changes
[ ] Documentation content changes
[ ] Testing
[ ] Other (please describe):

What is the current behavior?

This adds a helper utility to compute the witness in lieu of the final exponentiation for a miller loop output.

Issue Number: N/A

What is the new behavior?

There is no change in existing behaviour.

Does this introduce a breaking change?

[ ] Yes
[x] No

Other information

https://ia.cr/2024/640