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?
Roots are computed with generic nth_root(x) function, which takes ~2s to compute all required hints for BLS curve.
What is the new behavior?
By exploiting the group structure and clearing any 27th root of unity (instead of just primitive) all roots are now being computed by simple modular inverse exponentiations. This substantially improves the efficiency of hints computation.
Efficient hint computation for bls curves
Please check the type of change your PR introduces:
What is the current behavior?
Roots are computed with generic
nth_root(x)function, which takes ~2s to compute all required hints for BLS curve.What is the new behavior?
By exploiting the group structure and clearing any 27th root of unity (instead of just primitive) all roots are now being computed by simple modular inverse exponentiations. This substantially improves the efficiency of hints computation.
Does this introduce a breaking change?
Other information