ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 27 Jul 2017 13:19:06 +0200NIST B-283 Elliptic Curvehttps://ask.sagemath.org/question/8736/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.Thu, 23 Feb 2012 22:28:29 +0100https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/Comment by DSM for <p>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:</p>
<pre><code>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])
</code></pre>
<p>I get a fairly long traceback after the last line followed by:</p>
<pre><code>OverflowError: long int too large to convert to int
</code></pre>
<p>Any help is appreciated.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20251#post-id-20251Hmm. 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.<a> = FF(order, 'a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )[]` help any? [This changes the backend.]Thu, 23 Feb 2012 23:16:01 +0100https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20251#post-id-20251Answer by twoforone for <p>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:</p>
<pre><code>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])
</code></pre>
<p>I get a fairly long traceback after the last line followed by:</p>
<pre><code>OverflowError: long int too large to convert to int
</code></pre>
<p>Any help is appreciated.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13501#post-id-13501I 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.<a> = 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?Thu, 26 Apr 2012 10:21:22 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13501#post-id-13501Comment by dan_fulea for <p>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.<a> = FF(order, 'a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )[]</a></p><a>
<p>How could I get its order? In that, how could I find a random point of that curve?</p>
</a>https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=38413#post-id-38413The 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)*PThu, 27 Jul 2017 13:12:13 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=38413#post-id-38413Answer by MichaelJ for <p>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:</p>
<pre><code>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])
</code></pre>
<p>I get a fairly long traceback after the last line followed by:</p>
<pre><code>OverflowError: long int too large to convert to int
</code></pre>
<p>Any help is appreciated.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13299#post-id-13299Thanks 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.Fri, 24 Feb 2012 16:27:09 +0100https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13299#post-id-13299Comment by dan_fulea for <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:</p>
<pre><code>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])
</code></pre>
<p>no overflow... I think it's related to the b parameter.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=38414#post-id-38414This 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...Thu, 27 Jul 2017 13:19:06 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=38414#post-id-38414Comment by MichaelJ for <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:</p>
<pre><code>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])
</code></pre>
<p>no overflow... I think it's related to the b parameter.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20218#post-id-20218When 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?Mon, 27 Feb 2012 21:45:10 +0100https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20218#post-id-20218Comment by MichaelJ for <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:</p>
<pre><code>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])
</code></pre>
<p>no overflow... I think it's related to the b parameter.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20219#post-id-20219When I use sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pariMon, 27 Feb 2012 21:35:12 +0100https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20219#post-id-20219Comment by DSM for <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:</p>
<pre><code>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])
</code></pre>
<p>no overflow... I think it's related to the b parameter.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20248#post-id-20248It's related to b as a number, but not to anything EllipticCurve-related. Simply try `GF(2**283,'a')(2**64)`, which fails too.Fri, 24 Feb 2012 21:38:43 +0100https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=20248#post-id-20248Answer by twoforone for <p>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:</p>
<pre><code>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])
</code></pre>
<p>I get a fairly long traceback after the last line followed by:</p>
<pre><code>OverflowError: long int too large to convert to int
</code></pre>
<p>Any help is appreciated.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13535#post-id-13535Please, help to compute order of the above elliptic curve E using SAGE and libraries in sage?Thu, 03 May 2012 07:41:06 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13535#post-id-13535Answer by achrzesz for <p>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:</p>
<pre><code>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])
</code></pre>
<p>I get a fairly long traceback after the last line followed by:</p>
<pre><code>OverflowError: long int too large to convert to int
</code></pre>
<p>Any help is appreciated.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13502#post-id-13502 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
Thu, 26 Apr 2012 15:59:18 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13502#post-id-13502Comment by achrzesz for <pre><code>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
</code></pre>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=19860#post-id-19860 hex representation of P[0]:
w=P[0]
v=w.polynomial('a')
print hex(v.change_ring(ZZ)(2))
Fri, 27 Apr 2012 02:31:19 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=19860#post-id-19860Answer by achrzesz for <p>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:</p>
<pre><code>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])
</code></pre>
<p>I get a fairly long traceback after the last line followed by:</p>
<pre><code>OverflowError: long int too large to convert to int
</code></pre>
<p>Any help is appreciated.</p>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13503#post-id-13503 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 PPThu, 26 Apr 2012 17:58:32 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?answer=13503#post-id-13503Comment by achrzesz for <pre><code> 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
</code></pre>
https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=19861#post-id-19861n can be computed for example using schoof2 program from Miracl library
The curve order is 2nThu, 26 Apr 2012 19:49:46 +0200https://ask.sagemath.org/question/8736/nist-b-283-elliptic-curve/?comment=19861#post-id-19861