Ask Your Question

# Elliptic curves

F.<x> = GF(2)[]

K.<a> = GF(2**163, name='a', modulus=x^163 + x^7 + x^6 + x^3 +1 )

b = 0x000000020A601907B8C953CA1481EB10512F78744A3205FD

b1 = F(b.digits(2))

xx1 = 0x00000003F0EBA16286A2D57EA0991168D4994637E8343E36

yy1 = 0x00000000D51FBC6C71A0094FA2CDD545B11C5C0C797324F1

xx2 = F(xx1.digits(2))

yy2 = F(yy1.digits(2))

E = EllipticCurve(K,[1,1,0,0,b1])

punto = E([xx2,yy2])

punto.order()


When i try to find the order I got this error!

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "_sage_input_17.py", line 10, in <module>
exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cHVudG8ub3JkZXIoKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
File "", line 1, in <module>

File "/tmp/tmpLBskY6/___code___.py", line 2, in <module>
exec compile(u'punto.order()
File "", line 1, in <module>

File "/sagenb/sage_install/sage-5.4-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 3295, in order
N = generic.order_from_bounds(self,bounds,operation='+')
File "/sagenb/sage_install/sage-5.4-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/generic.py", line 1405, in order_from_bounds
m = d * bsgs(Q, identity, bounds, operation=operation)
File "/sagenb/sage_install/sage-5.4-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/groups/generic.py", line 475, in bsgs
for i0 in misc.srange(m):
File "/sagenb/sage_install/sage-5.4-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/sage/misc/misc.py", line 1185, in srange
return ZZ.range(start, end, step)
File "integer_ring.pyx", line 456, in sage.rings.integer_ring.IntegerRing_class.range (sage/rings/integer_ring.c:6534)
RuntimeError: Segmentation fault

edit retag close merge delete

## Comments

1

Running this code consumed all the RAM in my computer. Perhaps this has something to do with the error. What is your question?

( 2013-04-02 14:36:59 -0500 )edit

## 3 answers

Sort by » oldest newest most voted

Elliptic curves over very large binary fields are not well supported in Sage, so the code is here reverting to generic algorithms, which cannot cope with such large examples.

more

The given elliptic curve is one of the shape $y^2 + xy = x^3 +x^2 +b$ where $b$ is a multiplicative generator of the field GF( 2**p ) for the prime p = 163.

A part of the question was strictly "how to make the code run without error". Here is a piece of code that does the job in a similar more pacific situation.

First, we will construct such a situation over a smaller field. For this, we search for a smaller $p$, such that a corresponding polynomial $X^p + X^7 + X^6 + X^3 + 1$ is irreducible in $\mathbb{F}_2[X]$ . The code is:

F = GF(2)
R.<X> = PolynomialRing( F )
k = 7; n = 10                        # later: x = a^k, y = a^n
powers   = [ 2*k, 3*k, 2*n, k+n ]    # later: xx, xxx, yy, xy
minpower = min( powers )

for p in primes( 10000 ):
if p < 11:    continue
P = X^p + sum( [ X^(power - minpower) for power in powers ] )
if P.is_irreducible() :
print "p = %4s . The polynomial %s is irreducible over GF(2)[X]." % ( p, P )


And we get:

p =   13 . The polynomial X^13 + X^7 + X^6 + X^3 + 1 is irreducible over GF(2)[X].
p =   37 . The polynomial X^37 + X^7 + X^6 + X^3 + 1 is irreducible over GF(2)[X].
p =  163 . The polynomial X^163 + X^7 + X^6 + X^3 + 1 is irreducible over GF(2)[X].
p =  787 . The polynomial X^787 + X^7 + X^6 + X^3 + 1 is irreducible over GF(2)[X].
p = 3037 . The polynomial X^3037 + X^7 + X^6 + X^3 + 1 is irreducible over GF(2)[X].


So instead of 163 we take the 37 and the following code

R.<x> = PolynomialRing( GF(2) )
p     = 37    # one of 13, 37, 163, 787, 3037, ...
K.<a> = GF( 2**p, name='a', modulus=x^p + x^7 + x^6 + x^3 + 1 )
E = EllipticCurve( K, [1, 1, 0, 0, a^( p + minpower ) ] )

P = E.point( (a^7, a^10) )    # ( a^k, a^n ) is a point on the curve

Porder = P.order()
Eorder = E.order()

print "E has E( GF(2^%s) ) with order:   %s = %s" % ( p, Eorder.factor(), Eorder )
print "Let P be (a^7, a^10). P has order %s = %s" % ( Porder.factor(), Porder )


delivers:

E has E( GF(2^37) ) with order:   2 * 3 * 29 * 257 * 3073451 = 137438581818
Let P be (a^7, a^10). P has order 2 * 3 * 29 * 257 * 3073451 = 137438581818


Of course, p = 163 is too much, if we do not implement code especially for the situation. (And even if we manage to do it, next day we have the question related to p = 787 instead.)

more

How to fix this error or how to make I Get the order!

more

## Your Answer

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

Add Answer

## Stats

Asked: 2013-04-02 11:30:13 -0500

Seen: 195 times

Last updated: Mar 01