How long does it take to double and add points on an elliptic curve?

141 Views Asked by At

I have some problems understanding how many multiplications it takes to add or double points on an elliptic curve in Weierstrass form. This link tells that it's 11 and 14, but I don't quite understand why. Can someone walk me through it? The formulas are as following:

Doubling $P_1=(x_1,y_1)$: $$x_2=\lambda^2-2x_1 \textrm{ and } y_2=-\lambda x_2-(y_1-\lambda x_1) \text{, where } \lambda =\frac{f'(x)}{2y}=\frac{3x^2+b}{2y}.$$

Addition $P_1+P_2=(x_1,y_1)+(x_2,y_2)$: $$x_3=\lambda^2-x_1-x_2\text{ and } y_3=y_2=-\lambda x_2-(y_1-\lambda x_1),\text{ where } \lambda=\frac{y_2-y_1}{x_2-x_1}$$

1

There are 1 best solutions below

2
On

Me neither. For the first computation, I count at most 4 multiplications (and 1 addition) to get $\lambda$, then 2 multiplications (and 1 addition) to get $x_2$ and 2 multiplications (and 2 additions) to get $y_2$. So that's only 8 multiplications and some of them might be replaced by addition. On the other hand, I counted division as multiplication, which seems not wanted.