Ask Your Question
0

sage codes for double and add algorithm for scalar multiplication over elliptic curve over prime field

asked 2016-12-15 01:11:17 -0500

santoshi gravatar image

if point P is given and K is given find Q=KP

edit retag flag offensive close merge delete

Comments

Thank you very much sir for your reply but i want scalar multiplication by taking binary expansion of scalar.

for example if k=4 then(0100) the considering 1 and 0 the point add and double.(sage code)

santoshi gravatar imagesantoshi ( 2016-12-16 07:12:35 -0500 )edit

This is exactly what i did.

tmonteil gravatar imagetmonteil ( 2016-12-16 17:27:11 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2016-12-15 10:03:38 -0500

tmonteil gravatar image

updated 2016-12-15 14:01:20 -0500

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

  • if K=2*k is even, compute K*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, k 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)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-12-15 01:11:17 -0500

Seen: 561 times

Last updated: Dec 15 '16