# Scalar Multiplication for Elliptic Curve

Let $\mathbb{E}$ be the elliptic curve $y^2 = x^3 + 6x \text{ mod } 11$ and consider the point $P = (2, 3)$ on it. How do I compute $3P$?

I have been able to figure out what $2P$ is, $2P = (5,10)$. However I am unsure if even knowing $2P$ is helpful, or do I just compute $3P$ from knowing the original $P$?

• Have you looked at how addition is defined on elliptic curves, specifically point addition and point doubling? E.g. you can use point doubling to compute $Q = 2P$ and then use point addition to compute $3P = Q + P$. – puzzlepalace May 25 '16 at 23:14
• $3P=2P+P=(7,0)$. – user94293 May 25 '16 at 23:26

## 1 Answer

On standard way to compute scalar multiplication is to use Double-and-add algorithm:

The idea is to take the binary representation of your scalar $b = b_0 ... b_m$in your case $b = 3$ gives $b_0b_1 = 11$.

First you initialize your result $Q$ with $0$.

Then for each increasing bit index $i$, you set $Q = 2Q$ (computed with the doubling formula) and if $b_i = 1$ you set $Q = Q + P$ (computed with the addition formula).

In your example you have:

1. $Q = 0$

2. $Q = 2Q = 0$, $b_0 = 1$ then $Q = Q + P = P$

3. $Q = 2*Q = 2P$, $b_1 = 1$ then $Q = Q + P = 3P$

It is the generalization of user94293 comment. If your implementation is critical, be careful since the algorithm above is not time constant. You may prefer the Montgomery ladder in critical cases.

• Note: There are also other techniques to hide timing information including blinding. – SEJPM May 26 '16 at 9:12