Ask Your Question

# 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

## Comments

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

## 5 Answers

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

## Comments

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


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

## Comments

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.

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

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?

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

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
print P
print E.is_on_curve(P,P)  # OK

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

more

## Comments

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

    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,PP)
print n*PP
#True
#(0 : 1 : 0)     -->   n is equal to the order of PP
`
more

## Comments

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

## Your Answer

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

Add Answer

## Stats

Asked: 2012-02-23 22:28:29 +0200

Seen: 1,010 times

Last updated: May 03 '12