Why is exponentiation of points on elliptic curve so fast?

edit

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.

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"