CODEWITHSUNDEEP
mathpointsageelliptic-curve
user2059300
user2059300

Reputation: 361

SAGE - Listing points on an elliptic curve

I have a generated elliptic curve of a modulus. I want to list just a few points on it (doesn't matter what they are, I just need one or two) and I was hoping to do:

E.points()

However due to the size of the curve this generates the error:

OverflowError: range() result has too many items

I attempted to list the first four by calling it as such: 

E.points()[:4]

However that generated the same error

Is there any way I can make it list just a few points? Maybe some Sage function?

Upvotes: 1

Views: 2248

Answers (1)

MvG
MvG

Reputation: 60908

Since you did not include code to reproduce your situation, I take an example curve from the Sage documentation:

sage: E = EllipticCurve(GF(101),[23,34])

Generating random points

You can repeatedly use random_element or random_point to choose points at random:

sage: E.random_point()
(99 : 92 : 1)
sage: E.random_point()
(27 : 80 : 1)

This is probably the simplest way to obtain a few arbitrary points on the curve. random_element works in many places in Sage.

Intersecting with lines

It has the defining polynomial

sage: p = E.defining_polynomial(); p
-x^3 + y^2*z - 23*x*z^2 - 34*z^3

which is homogeneous in x,y,z. One way to find some points on that curve is by intersecting it with straight lines. For example, you could intersect it with the line y=0 and use z=1 to choose representatives (thus omitting representatives at z==0) using

sage: p(y=0,z=1).univariate_polynomial().roots(multiplicities=False)
[77]

So at that point you know that (77 : 0 : 1) is a point on your curve. You can automate things, intersecting with different lines until you have reached the desired number of points:

sage: res = []
sage: y = 0
sage: while len(res) < 4:
....:     for x in p(y=y,z=1).univariate_polynomial().roots(multiplicities=False):
....:         res.append(E((x, y, 1)))
....:     y += 1
....:
sage: res[:4]
[(77 : 0 : 1), (68 : 1 : 1), (23 : 2 : 1), (91 : 4 : 1)]

Adapting points()

You can have a look at how the points() method is implemented. Type E.points?? and you will see that it uses an internal method called _points_via_group_structure. Looking at the source of that (using E._points_via_group_structure?? or the link to the repo), you can see how that is implemented, and probably adapt it to only yield a smaller result. In particular you can see what role that range plays here, and use a smaller range instead.

Upvotes: 2

Related Questions