Ask Your Question
1

Elliptic curves

asked 2013-04-02 18:30:13 +0100

Weisien gravatar image

updated 2015-01-13 21:01:07 +0100

FrédéricC gravatar image
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 flag offensive 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?

fidbc gravatar imagefidbc ( 2013-04-02 21:36:59 +0100 )edit

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

Weisien gravatar imageWeisien ( 2013-04-03 02:46:02 +0100 )edit

2 Answers

Sort by » oldest newest most voted
2

answered 2013-12-15 07:50:54 +0100

John Cremona gravatar image

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.

edit flag offensive delete link more
2

answered 2017-03-01 12:52:08 +0100

dan_fulea gravatar image

updated 2017-04-12 22:25:00 +0100

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

# ========================================

Postlude, later edit:

The given curve $$ E\ :\ y^2 +xy = x^3 +x^2 + b $$ has the order twice the prime $$ 5846006549323611672814742442876390689256843201587\ .$$ In my hands, sage can only verify this order:

q = 2^163

R.<X> = PolynomialRing( GF( 2 ) )
F.<a> = GF( q, modulus = X^163 + X^7 + X^6 + X^3 + 1 )

b1 = 0x000000020A601907B8C953CA1481EB10512F78744A3205FD
b  = F( b1.digits(2) )

PRIME = 5846006549323611672814742442876390689256843201587
ORDER = 2*PRIME

print "hex( q+1 - 2sqrt(q) ) is %s" % hex( ceil( q+1 - 2*sqrt(q) ) ) 
print "hex( ORDER          ) is %s" % hex( ORDER                   ) 
print "hex( q+1 + 2sqrt(q) ) is %s" % hex( ceil( q+1 + 2*sqrt(q) ) ) 

print "\nIs PRIME = %s indeed a prime? %s" % ( PRIME, PRIME.is_prime() )
print "ORDER = 2*PRIME" 

E = EllipticCurve( [1,1,0,0,b] )
P = E.random_point()
print "\nE is the elliptic cuve for the data [1,1,0,0,b]"
print "P is a random point on E( GF(q) )"
print "ORDER * P = %s" % ( ORDER * P )

This gives:

hex( q+1 - 2sqrt(q) ) is 7fffffffffffffffffffa57d86660310cdbdd3415
hex( ORDER          ) is 80000000000000000000525fcefce182548469866
hex( q+1 + 2sqrt(q) ) is 800000000000000000005a827999fcef32422cbee

Is PRIME = 5846006549323611672814742442876390689256843201587 indeed a prime? True
ORDER = 2*PRIME

E is the elliptic cuve for the data [1,1,0,0,b]
P is a random point on E( GF(q) )
ORDER * P = (0 : 1 : 0)

As said, my sage knowledge could not help to find the order by using only sage. After some time, i tried to attack the order of the "weaker" curve $E_0$, which is a twist of $E$: $$ E_0\ :\ y^2 +xy = x^3 + b \ .$$

It is simple to check $|E(\mathbb F_q)| + |E_0(\mathbb F_q)|=2(q+1)$.

So getting the order for $E$ is equivalent to getting it for $E_0$. The situation for $E_0$ is as follows

E0 = EllipticCurve( F, [1,0,0,0,b] )
P0 = E0.random_point()

ORDER0 = 2*(q+1) - ORDER

print "\nE0 is the elliptic cuve for the data [1,1,0,0,b]"
print "E0 has order %s" % ( ORDER0.factor() )
print "Let us check this. P0 is a random point on E0( GF(q) )"
print "ORDER0 * P0 = %s" % ( ORDER0 * P0 )

This gives:

E0 is the elliptic cuve for the data [1,1,0,0,b]
E0 has order 2^2 * 31 * 907 * 18908293 * 192478327 * 28564469476693963307545101353
Let us check this. P0 is a random point on E0( GF(q) )
ORDER0 * P0 = (0 : 1 : 0)

It is simple to get some "canonical" (i.e. non-random) points on this curve, for instance $(c,c^2)$ where $c$ is a fourth root of $b$. Its order is four.

sage: c  = b^( q/4 );
sage: P1 = E0.point( (c,c^2) )
sage: P1.order()
4

Or for $c$ a cubic root of $b$ the point $(c,c)$, which generates.

c = b^( (2*(q-1)+1)/3 )
P0 = E0.point( (c,c) )

# This is a point of full order, since:

for div in ORDER0.prime_factors():
    print "Is (ORDER0 / %s ) * P0 zero? %s" % ( div, ( ZZ( ORDER0 / div ) * P0 ) .is_zero() )

Results:

Is (ORDER0 / 2 ) * P0 zero? False
Is (ORDER0 / 31 ) * P0 zero? False
Is (ORDER0 / 907 ) * P0 zero? False
Is (ORDER0 / 18908293 ) * P0 zero? False
Is (ORDER0 / 192478327 ) * P0 zero? False
Is (ORDER0 / 28564469476693963307545101353 ) * P0 zero? False

An other point on $E_0$ is $(c^2,c^3)$ where $c$ is a fifth order root of $b$ in $F$. Its order is not maximal. (It drops by the factor $31$.)

c = b^( (2*(q-1)+1)/5 )
P5 = E0.point( (c^2,c^3) )

# This is a point of full order, since:

for div in ORDER0.prime_factors():
    print "Is (ORDER0 / %s ) * P5 zero? %s" % ( div, ( ZZ( ORDER0 / div ) * P5 ) .is_zero() )

Results:

Is (ORDER0 / 2 ) * P5 zero? False
Is (ORDER0 / 31 ) * P5 zero? True
Is (ORDER0 / 907 ) * P5 zero? False
Is (ORDER0 / 18908293 ) * P5 zero? False
Is (ORDER0 / 192478327 ) * P5 zero? False
Is (ORDER0 / 28564469476693963307545101353 ) * P5 zero? False

So the "weaker" (twisted) curve is not weak enough for me.

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2013-04-02 18:30:13 +0100

Seen: 1,408 times

Last updated: Apr 12 '17