# 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"

edit retag close merge delete

Sort by » oldest newest most voted

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

more

Hi

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"

more

It 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 seconds

( 2019-05-30 15:36:51 +0200 )edit

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

( 2020-05-29 10:18:09 +0200 )edit