1
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – puzzlepalace
    Commented May 25, 2016 at 23:14
  • 2
    $\begingroup$ $3P=2P+P=(7,0)$. $\endgroup$
    – user94293
    Commented May 25, 2016 at 23:26

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Note: There are also other techniques to hide timing information including blinding. $\endgroup$
    – SEJPM
    Commented May 26, 2016 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.