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.Fri, 29 May 2020 10:18:09 +0200Why is exponentiation of points on elliptic curve so fast?https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/I am working on elliptic curves in sagemath. I was trying to collect benchmarks for group operation and exponentiation of points on NIST P-256 elliptic curve. When I tried to perform a group operation on 2 points on the curve, it takes roughly 2 micro seconds. When I tried to perform exponentiation on a point in elliptic curve with a random exponent, it takes only 3 micro seconds. How is this even possible? Since I am exponentiating with a 256 bit value, this should at least take time required for 256 group operations, which is more than 1ms. I am worried if my code is wrong!
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"Thu, 30 May 2019 05:50:46 +0200https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/Answer by nbruin for <p>I am working on elliptic curves in sagemath. I was trying to collect benchmarks for group operation and exponentiation of points on NIST P-256 elliptic curve. When I tried to perform a group operation on 2 points on the curve, it takes roughly 2 micro seconds. When I tried to perform exponentiation on a point in elliptic curve with a random exponent, it takes only 3 micro seconds. How is this even possible? Since I am exponentiating with a 256 bit value, this should at least take time required for 256 group operations, which is more than 1ms. I am worried if my code is wrong! </p>
<pre><code>p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
</code></pre>
https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?answer=46727#post-id-46727Note that by constructing the group in the way you do, you get a group that is explicitly represented as an additive cyclic group (with an explicit generator). When you create random elements, the system probably just takes an appropriate random element by taking a random multiple of the generator *and store it as such*.
As a consequence, if you then compute a multiple of THAT point, the system only has to multiply two integers and take it mod the order of the group to represent the element as a multiple of the generator. You're basically avoiding the discrete log problem by never taking "discrete exponentials". When you print the element, it looks like sage does perform the "discrete exp" (i.e., find the coordinate representation of the point).
If you take the use of the wrapper out and time something like
Integer(exponent[i])*E.gen(0)
you get something more realistic, like 0.01 seconds per operation.Thu, 30 May 2019 20:48:10 +0200https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?answer=46727#post-id-46727Answer by ortollj for <p>I am working on elliptic curves in sagemath. I was trying to collect benchmarks for group operation and exponentiation of points on NIST P-256 elliptic curve. When I tried to perform a group operation on 2 points on the curve, it takes roughly 2 micro seconds. When I tried to perform exponentiation on a point in elliptic curve with a random exponent, it takes only 3 micro seconds. How is this even possible? Since I am exponentiating with a 256 bit value, this should at least take time required for 256 group operations, which is more than 1ms. I am worried if my code is wrong! </p>
<pre><code>p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
</code></pre>
https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?answer=46706#post-id-46706Hi
maybe there exist cells where variables are declared elsewhere in your notebook.
because I have to modify slightly your code !.
anyway now the time is about 3 or 4 seconds for my PC.[edited I misplaced the first t1 ;-) , but maybe what I did it's not what you wanted to evaluate ?]
import time
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
e=0
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time.time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time.time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
t1 = time.time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time.time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"Thu, 30 May 2019 08:00:08 +0200https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?answer=46706#post-id-46706Comment by panther for <p>Hi</p>
<p>maybe there exist cells where variables are declared elsewhere in your notebook.
because I have to modify slightly your code !.
anyway now the time is about 3 or 4 seconds for my PC.[edited I misplaced the first t1 ;-) , but maybe what I did it's not what you wanted to evaluate ?]</p>
<pre><code>import time
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
e=0
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time.time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time.time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
t1 = time.time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time.time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
</code></pre>
https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?comment=46715#post-id-46715It took around 5 seconds for executing G = E.abelian_group(). But after that is done, for the exponentiation is taking very less time. I don't see any reason how exponentiation could be done so fast. Here is my output for your code.
Time per operation = 2.93278694153e-06 seconds
Time per operation = 2.42040157318e-06 secondsThu, 30 May 2019 15:36:51 +0200https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?comment=46715#post-id-46715Comment by John Cremona for <p>Hi</p>
<p>maybe there exist cells where variables are declared elsewhere in your notebook.
because I have to modify slightly your code !.
anyway now the time is about 3 or 4 seconds for my PC.[edited I misplaced the first t1 ;-) , but maybe what I did it's not what you wanted to evaluate ?]</p>
<pre><code>import time
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
e=0
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time.time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time.time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
t1 = time.time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time.time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
</code></pre>
https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?comment=51627#post-id-51627If yo upick random points on E rather than random elements of the abelian group then I think you will find that the time taken is longer. In your code you are only doing group operations in an abstract abelian group (either cyclic or possibly with two cyclic factors) so the operation is just one (or at most 2) integer modular multiplcations.Fri, 29 May 2020 10:18:09 +0200https://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/?comment=51627#post-id-51627