Ask Your Question
0

NIST B-283 Elliptic Curve

asked 2012-02-23 15:28:29 -0600

MichaelJ gravatar image

updated 2015-01-13 14:35:04 -0600

FrédéricC gravatar image

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

DSM gravatar imageDSM ( 2012-02-23 16:16:01 -0600 )edit

5 answers

Sort by » oldest newest most voted
0

answered 2012-02-24 09:27:09 -0600

MichaelJ gravatar image

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.

edit flag offensive delete link 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.

DSM gravatar imageDSM ( 2012-02-24 14:38:43 -0600 )edit

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

MichaelJ gravatar imageMichaelJ ( 2012-02-27 14:35:12 -0600 )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?

MichaelJ gravatar imageMichaelJ ( 2012-02-27 14:45:10 -0600 )edit
0

answered 2012-04-26 10:58:32 -0600

achrzesz gravatar image
    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
edit flag offensive delete link more

Comments

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

achrzesz gravatar imageachrzesz ( 2012-04-26 12:49:46 -0600 )edit
0

answered 2012-04-26 08:59:18 -0600

achrzesz gravatar image
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
edit flag offensive delete link more

Comments

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

achrzesz gravatar imageachrzesz ( 2012-04-26 19:31:19 -0600 )edit
0

answered 2012-05-03 00:41:06 -0600

twoforone gravatar image

updated 2012-05-03 00:43:10 -0600

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

edit flag offensive delete link more
0

answered 2012-04-26 03:21:22 -0600

twoforone gravatar image

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?

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2012-02-23 15:28:29 -0600

Seen: 525 times

Last updated: May 03 '12