Overflow when defining points on elliptic curve

I have the following elliptic curve in SAGE:

p1 = 2^256-189
E10 = EllipticCurve(GF(p1),[-3,0])


I want to find points of different orders and multiply them with a number. However when I try to get SAGE to define or print a point like P=E10.points()[19] I get the following error:

Error in lines 1-1
Traceback (most recent call last):
File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute
exec compile(block+'\n', '', 'single') in namespace, locals
File "", line 1, in <module>
File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 214, in points
v = self._points_via_group_structure()
File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 156, in _points_via_group_structure
for m in range(1,ni[0]):
OverflowError: Python int too large to convert to C long


So far I have only suceeded in finding the point (0,0) of order 2 but I also need points of higher order. Is there any way to fix this overflow error or find points of different orders that SAGE can actually handle without getting overflow or is my curve just impossible to work with?

I started out trying to print the list of all points and their orders but that resulted in the error. Then I tried printing only one point and now I am simply trying to define the points without printing them (however I need to print k*P for some k later on for all the points).

I got the point (112810383992036387042877104932833846002363090508032041943368137894367452952778,85347934490306136025376423714596250175969011873639765034628869535783033211301) using E10.gens() but I can't define it getting the error:

ValueError: libGAP: Error, E: <n> must be a positive integer (not a integer (>= 2^60))


So I am suspecting that it is not possible to get any useful points on this curve. If so can anyone explain to me why it is so (with some references if possible)?

edit retag close merge delete

The error you encounter:

ValueError: libGAP: Error, E: <n> must be a positive integer (not a integer (>= 2^60))


has nothing to do with elliptic curves: Your elliptic curve is called E10, not E. You;d make it easier to diagnose if you'd include the exact command that triggered the error for you. E by default is bound to a function that constructs n-th roots of unity (don't ask me how THAT escaped into the global namespace!)

( 2017-02-26 18:45:44 +0100 )edit
1

That is weird since I don't have a curve named E in my code. I just tried to say E10(x,y). But I have got the points I need now thanks to the answers

( 2017-02-28 11:06:26 +0100 )edit

Sort by » oldest newest most voted

I have no problems to investigate some points on the curve. For instance:

E10 = EllipticCurve( GF(p1), [-3,0] )
P,  = E10.gens()
E10.gens() == [ P, ]    # True

print P.order().factor()
# 2^2 * 17 * 31 * 43 * 23081 * 4552451 * 188515208046969049479851413 * 64490171990641492934559272183431339

k = P.order() / 17
k = ZZ(k)
Q = k * P
x, y, _ = Q
print "k = %s" % k
print "Q = k*P"
print "Q has the following coordinates x, y:"
print "x = %s" % x
print "y = %s" % y


After a %cpaste into the interpreter:

True
2^2 * 17 * 31 * 43 * 23081 * 4552451 * 188515208046969049479851413 * 64490171990641492934559272183431339
k = 6811299366900952671974763824040465167839410862684739061144563765171360567044
Q = k*P
Q has the following coordinates x, y:
x = 27437129805757554196750179718248270297390475505636928792989955318129458214854
y = 72861835628999598253805209504126577415537834053407849625158220308472740134763


More cannot be reproduced. We need the print commands and the points to be printed.

more

Thank you very much! This is perfect and does the job immediately!

( 2017-02-26 14:31:01 +0100 )edit

The problem almost certainly is that the list of points that E10.points() is supposed to produce will never fit in memory. Working with points is easy enough, and they are easy to find: for about half of the values of x, x^3-3*x will be a square in your field. You can just do arithmetic with those points, e.g.:

sage: k=E10.base_field()
sage: P=E10(1,sqrt(k(1^3-3*1)))

more

Can you explain how you knew that would be a point on the curve and how to generate others? Every point I try is not on the curve. I just need to find points of orders 17, 31, 43, 23081. 4552451, 188515208046969049479851413 and 64490171990641492934559272183431339 that SAGE can handle doing calculations with

( 2017-02-23 19:09:51 +0100 )edit

If you randomly try elements from your field x0, you'll find that for about half of them, x0^3-3*x0 is a square, so you can construct points with those:

sage: len([a for a in [1..500] if k(a^3-3*a).is_square()])
246


This curve is easy enough for sage to actually find the group structure automatically:

sage: G=E10.abelian_group()


so you could just use that to see that G is cyclic and find a generator. It's then trivial to compute multiples of that generator that have the required prime order.

( 2017-02-23 21:01:16 +0100 )edit

That is very helpful. Thank you. I have defined G and found a generator point P. I know that there will be subgroups generated by points of the orders I want since G is cyclic. I am still learning SAGE so would you be so kind to explain how I can find those points using SAGE? I don't know a lot of commands but I am trying to learn

( 2017-02-25 12:26:49 +0100 )edit

Just compute the appropriate multiples of P by scalar multiplication. 2*P will give you twice the point, 3*P will give you three times the point etc.

( 2017-02-26 07:02:34 +0100 )edit

Oh. I thought there was some smart command to get the generators of the cyclic subgroups or something like that. Thank you very much for your help

( 2017-02-26 14:31:43 +0100 )edit