Revision history [back]

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

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.

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.