Number of points on elliptic curve

Question

If you have an elliptic curve in the form of:

y^2 = x^3 + a*x + b (mod p)

Is there a good program to calculate the number of points on this curve?

I have read about Schoof's and Schoof-Elkies-Atkin (SEA) algorithm, but I'm looking for open source implementations. Does anyone know a good program that can do this?

Also if a is 1 and b is 0, the SEA algorithm can't be used because the j-invariant is 0. Is this correct?

Edit: this is in the context of elliptic-curve cryptography

Answer 1

Have you heard of Sage?

Sage includes Pari, which is an open source package for number theory. Pari has an implementation of SEA.

From http://wstein.org/papers/2008-bordeaux/sphinx/elliptic_curves.html#schoof-elkies-atkin-point-counting:

sage: k = GF(next_prime(10^20))
sage: E = EllipticCurve(k.random_element())
sage: E.cardinality()                   # less than a second
100000000005466254167

Answer 2

I have tried Sage. It took me around 3-4 hours to compile to x64 ubuntu. It seems to be a good program. But when the j-invariant is 0 the SEA algorithm can't be used, and then it seems to have some problems if you use large values for p/k.

After searching some more I also found miracl: http://www.shamus.ie/index.php?page=elliptic-curves They have implementations for both the normal Schoof and SEA algorithm. But this program also has some problems when using large input values. After 3-4 hours of running it crashed :/. I tried to fix it, and currently it's running again so hopefully it will work.

Edit: It works now. The program in the link above is identical to the one Rasmus Faber gave.

Answer 3

There are some links here: Implementations of portions of the P1363 draft.