Geek Answers Handbook

The number of points on an elliptic curve

If you have an elliptic curve in the form:

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

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

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

Also, if a is 1 and b is 0, the SEA algorithm cannot be used since the j-invariant is 0. Is this correct?

Edit: this is in the context of cryptography with an elliptic curve

+6
cryptography elliptic-curve
source share
4 answers

There are some links here: Implementation of parts of the P1363 project .

+1
source share

Have you heard of Sage ?

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

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
+1
source share

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

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

Edit: Now it works. The program mentioned in the link above is identical to the one given by Rasmus Faber.

+1
source share

I also used Mike Scott's program (miracl) for this purpose. Just curious, may I ask: how big were the domains with a simple batch order that you could create using software? I got to 1024 bits and now quit because I need my office PC for something other than weekly scoring software. Did you create larger domains? If so, I would be happy to receive the domain settings, and if you have no objection, they will be included in my academic signature ECC-Software.

My domains can be found here ECC Domain Page . Software for their use is available here. Manual with a link to the download page.

Relationship Michael Anders

+1
source share

More articles:


All Articles