CODEWITHSUNDEEP
cryptographyelliptic-curve
Omega
Omega

Reputation: 365

Number of points on elliptic curve

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?

Upvotes: 7

Views: 6390

Answers (4)

Rasmus Faber
Rasmus Faber

Reputation: 49647

There are some links here: Implementations of portions of the P1363 draft (wayback backup link of this page).

Upvotes: 1

Michael Anders
Michael Anders

Reputation: 41

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.

Upvotes: 2

Omega
Omega

Reputation: 365

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.

Upvotes: 1

Bobby Moretti
Bobby Moretti

Reputation: 717

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

Upvotes: 3

Related Questions