Overflow when defining points on elliptic curve

asked 2017-02-23 13:27:27 +0100

Alice
23 ●2 ●2 ●5

updated 2022-04-14 10:57:38 +0100

FrédéricC

5311 ●4 ●44 ●118

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 flag offensive close merge delete

Comments

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!)

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

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

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

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2017-02-26 12:11:38 +0100

dan_fulea
5537 ●5 ●43 ●95

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.

edit flag offensive delete link

Comments

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

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

add a comment

answered 2017-02-23 17:58:39 +0100

nbruin
4153 ●3 ●45 ●91

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)))

edit flag offensive delete link

Comments

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

Alice ( 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.

nbruin ( 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

Alice ( 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.

nbruin ( 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

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

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Overflow when defining points on elliptic curve

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Overflow when defining points on elliptic curve edit

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Overflow when defining points on elliptic curve