Computing $nQ$

Recall from yesterday that computers can compute $a^m \pmod{n}$ very quickly, even if $m$ is huge. They do this by writing $n$ in binary and doing a few squares and multiplies. Likewise, we can compute $nQ$ quickly when $Q$ is a point on an elliptic curve modulo $p$ . Try it out!

sage: p = 137
sage: F = FiniteField(p)
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
sage: P = E.random_element()
sage: print P
(96 : 94 : 1)

sage: time 102000823098320*P
(86 : 60 : 1)
CPU time: 0.12 s,  Wall time: 0.13 s

sage: show(plot(P) + plot(102000823098320*P,rgbcolor=(1,0,0)))
[[a plot]]

Now try with an elliptic curve over a huge field.

sage: p = next_prime(randrange(10^40))
sage: print p
sage: F = FiniteField(p)
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
sage: P = E.random_element()
sage: print P
554146695875703931136550843186162763121
(493257625218361211096484901389666856690 : 
         286863248034562484128552069228984577311 :
1)

Then multiply...

sage: time 909238403284092384209482038402*P
(151371634043111300277840422027192273952 : 
       333732213371771487412281506530764174375 :
1)
CPU time: 0.20 s,  Wall time: 0.21 s