redox-ecc icon indicating copy to clipboard operation
redox-ecc copied to clipboard

Reduce amount of modular reduction calls in point add/double

Open capito27 opened this issue 4 years ago • 0 comments

Another low-ish hanging fruit for #10.

When two integers of a maximal bit size are added together, the result takes at most 1 more bit to store. That property can be taken advantage of such that the modular reduction in the point addition and doubling formulas can mostly be ignored when adding two primefield elements together.

This will end up getting corrected by itself the next time those elements are multiplied together, and it brings some quite nice performance improvements.

In the order of 70% faster point addition / point-scalar multiplication for P-521, and slightly smaller improvements for the other weierstrass curves.

I also took the time to do the same for the other curves, but their new behaviour haven't been tested, as such feel free to let me know if you want me to revert those specific changes.

PS : here is a criterion report highlighting the performance gains on my system criterion.zip

capito27 avatar Jun 22 '20 22:06 capito27