Elliptic curves

edit

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.

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.