# NIST B-283 Elliptic Curve

I'm new to Sage so forgive me if this is simple. I am trying to define the NIST B-283 elliptic curve as follows:

def B283_test():
order = 2**283
a = 1
b = 0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5
K.<x>= GF(2)[]
K.<a> = GF(order=order, name='a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )
B283_curve = EllipticCurve(K, [1,a,0,0,b])


I get a fairly long traceback after the last line followed by:

OverflowError: long int too large to convert to int


Any help is appreciated.

edit retag close merge delete

Hmm. Looks like something is wrong with GF at large order. Does using FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari; K. = FF(order, 'a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )[] help any? [This changes the backend.]

( 2012-02-23 23:16:01 +0200 )edit

Sort by » oldest newest most voted

I want to know the order of the curve that have been built above i.e K283_curve.order(). Is there a way to know the order of that curve and in that how could I generate a random point which is element of that curve? this works fine FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari;K. = FF(order, 'a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )[]

How could I get its order? In that, how could I find a random point of that curve?

more

The following code constructs the Koblitz curve of MichaelJs answer. There is no relation to the posted B283.

R.<x>= GF(2)[]
K.<a> = GF( 2**283, modulus = x^283 + x^12 + x^7 + x^5 + 1 )
K283 = EllipticCurve( K, [1,0,0,0,1] )


The order is known: $$2^k+1-(w^k+\bar w^k)\ , \ w=\frac 12(-1+\sqrt{-7})\ ,\ k=283\ .$$ We compute it:

KK.<u> = QuadraticField( -7 )
ord = ZZ( 2^k + 1 - ( w^k + w.conjugate()^k ) )
print "The order of the Koblitz curve K283 is theoretically (hex):\n%s" % hex(ord)
print "It factorizes as:\n%s" % ZZ(ord).factor()


and get

The order of the Koblitz curve K283 is theoretically (hex):
7ffffffffffffffffffffffffffffffffffa6b8bb41d5dc9977fdfe511478187858f184


Then one repeats:

P = K283.random_point(); ord*P; ZZ(ord/2)*P

( 2017-07-27 13:12:13 +0200 )edit

Thanks DSM. I no longer get the overflow. For what it's worth the K283 curve seems to work and the only real differences are the a and b invariants:

def K283_test():
order = 2**283
a = 0
b = 1
K.<x>= GF(2)[]
K.<a> = GF(order=order, name='a', modulus=x^283 + x^12 + x^7 + x^5 + 1  )
K283_curve = EllipticCurve(K, [1,a,0,0,b])


no overflow... I think it's related to the b parameter.

more

It's related to b as a number, but not to anything EllipticCurve-related. Simply try GF(2**283,'a')(2**64), which fails too.

( 2012-02-24 21:38:43 +0200 )edit

When I use sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari

( 2012-02-27 21:35:12 +0200 )edit

When I use sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari, I get different methods in the Class EllipticCurve and some I would like aren't there (like random_point). Any recommendations on how to handle this other than (attempting to) write these myself?

( 2012-02-27 21:45:10 +0200 )edit

This is one of the two Koblitz curves, already defined over $\mathbb F_2$, considered then over the bigger field. It has predicted order, and the given curve in the post has nothing to do with the Koblitz curve. There are a plenty of realizable orders of elliptic curves in the Hasse interval around $q+1$, $q=2^{283}$, and the post wants information about a specific one...

( 2017-07-27 13:19:06 +0200 )edit

Please, help to compute order of the above elliptic curve E using SAGE and libraries in sage?

more
b =  0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5
Z.<x>=GF(2)[]
K.<a>=GF(2^283,'a',modulus=x^283 + x^12 + x^7 + x^5 + 1)
bb=Z(b.digits(2))
E=EllipticCurve(K,[1,1,0,0,bb])
P=E.random_element()
print P[0]
print P[1]
print E.is_on_curve(P[0],P[1])  # OK

# I was not able  to compute the order
# print E.order()   exhausts memory and exits

more

hex representation of P[0]: w=P[0] v=w.polynomial('a') print hex(v.change_ring(ZZ)(2))

( 2012-04-27 02:31:19 +0200 )edit
    b =  0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5
Z.<x>=GF(2)[]
K.<a>=GF(2^283,'a',modulus=x^283 + x^12 + x^7 + x^5 + 1)
bb=Z(b.digits(2))
E=EllipticCurve(K,[1,1,0,0,bb])
x=0x5f939258db7dd90e1934f8c70b0dfec2eed25b8557eac9c80e2e198f8cdbecd86b12053
y=0x3676854fe24141cb98fe6d4b20d02b4516ff702350eddb0826779c813f0df45be8112f4
n=7770675568902916283677847627294075626569625924376904889109196526770044277787378692871
xx=Z(x.digits(2))
yy=Z(y.digits(2))
PP=E(xx,yy)
print E.is_on_curve(PP[0],PP[1])
print n*PP
#True
#(0 : 1 : 0)     -->   n is equal to the order of PP
`
more

n can be computed for example using schoof2 program from Miracl library The curve order is 2n

( 2012-04-26 19:49:46 +0200 )edit