Revision history [back]

If i understand correctly, you want to decompose k in binary and:

compute 2kP with kP+kP
compute (2k+1) with kP+k*P+P

So, you can do recursively:

sage: E = EllipticCurve(GF(144169),j=1728)
sage: def mult(P,k):
....:     if k == 0:
....:         return E(0)
....:     elif k%2 ==1:
....:        return P + mult(P+P,k//2)
....:     else:
....:        return mult(P+P,k//2)

And check:

sage: P = E.random_element() ; P
(46104 : 85327 : 1)
sage: mult(P,13)
(128944 : 11188 : 1)
sage: 13*P
(128944 : 11188 : 1)

If i understand your question correctly, you want to decompose k K in binary and:

if K=2*k is even, compute 2K*P from k*P+k*P

if K=2*k+1 is odd, compute K*P from k*P+k*P+P

In both cases, kP with kP+kP

compute (2k+1) with kP+k*P+P

corresponds to shifting the binry representation of K to the right (and forget the first bit).

So, you can do recursively:

sage: E = EllipticCurve(GF(144169),j=1728)
sage: def mult(P,k):
....:     if k == 0:
....:         return E(0)
....:     elif k%2 ==1:
....:        return P + mult(P+P,k//2)
....:     else:
....:        return mult(P+P,k//2)

And check:

sage: P = E.random_element() ; P
(46104 : 85327 : 1)
sage: mult(P,13)
(128944 : 11188 : 1)
sage: 13*P
(128944 : 11188 : 1)