Revision history [back]
 | 1 | initial version |
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.)
| | 2 | No.2 Revision |
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.
