Menu
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?
622
Let E/Fq be an elliptic curve over a small field where we can easily compute its number of points N. Let t = 1+q −N and write P(X) = X2 −tX +q = (X −α)(X −β). Then for every n #E(Fqn ) = (1 − αn)(1 − βn).
2. If x2 = x1 and y2 = −y1, that is P = (x1,y1) and Q = (x2,y2) = (x1,−y1) = −P, then P + Q = O. Therefore 2P = (x3,y3) = (7,12).
The order of a point on an elliptic curve is the order of that point as an element of the group defined on the curve. = O, and m P = O for all integers 1 ≤ m < m. If such m exists, P is said to have finite order, otherwise it has infinite order.
The elliptic curve is defined by y2=x3+3x+1 in GF(7). My solution to check whether or not the point is on the curve was to substitute the point into the equation: (1)2=(2)3+3(1)+1. From inspection one may observe the left side does not equal the right side, therefore, the point is not on the curve.
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
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.
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
