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

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 2

I have been using Mike Scotts program(miracl) for this purpose also. Being just curious may I ask: How large were the domains with prime group order you could produce with the software? I got up to 1024 bit and now quit because I need my office PC for something other than running point counting software for weeks on end. Did you produce larger domains? If so I would be glad to get the domain parameters and if you don't have objections would include them in my ECC-Software Academic Signature.

My domains can be found here ECC Domain Page. The software to use them with is accessible from here Manual with Link to download page

Regards Michael Anders

Answer 3

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 4

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