Implement point counting for curves

AntonKueltz / fastecdsa

Python library for fast elliptic curve crypto

https://pypi.python.org/pypi/fastecdsa

The Unlicense

264 stars 77 forks source link

Implement point counting for curves #32

Closed AntonKueltz closed 2 years ago

AntonKueltz commented 5 years ago

Implement point counting for arbitrary elliptic curves. Validate by computing and comparing to the published values for standardized curves. Start with Schoof C implementation, and if too slow move to SEA. Sub-tasks -

Implement computation of Frobenius trace mod small primes in GMP C
Implement CRT using GMP C (or investigate if iterative is better as we compute Frobenius trace mod small primes)
Consolidate into algorithm and expose to python via C extension

shikuk commented 4 years ago

Do you know about MIRACL library ? It was the best implementation helped me, when i tryed to learn more, than theory, about this two algoritms

AntonKueltz commented 4 years ago

Thanks for the reference, don't think I've come across that lib. The implementation itself isn't that tricky conceptually but it ends up being a lot of code due to the need for polynomial math (which GMP is lacking support for, and I don't want to pull in another C dependency, Windows being a complete disaster with GMP is already bad enough).

It's really a matter of not currently having the will to spend a big chunk of time implementing this feature when it has such a little payoff since all curves that should be considered for serious use already have the number of points as a parameter.

AntonKueltz commented 2 years ago

Closing as wontfix because the lift (implementing polynomial fields or pulling in another math lib on top of GMP) doesn't match the payoff of point counting, which is adjacent to this libraries main purpose (providing support for ECDSA). If anyone needs this functionality they are welcome to add it and open a PR the changes.