2

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

MBrown
  • 551
  • The wikipage specifies Weierstrass form with projective coordinates. Using projective coordinates allows you to do without that costly division. You do have to do one division - at the end, after a fed hundred point doublings and additions. The formulas are a little bit more complicated for projective coordinates, but you save yourself from that time consuming division in each iteration for a significant overall gain. – Jyrki Lahtonen Nov 01 '14 at 14:33

1 Answers1

0

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.

Hagen von Eitzen
  • 374,180
  • I should probably mention that we work over a field, so it is modular division. So every time we divide we do an extended Euclid's algorithm. – MBrown Oct 28 '14 at 11:49
  • In the wikipage it says that the cost of an inversion is estimated to be 100 times that of a multiplication. Extended Euclid's algorithm is fast but not instantaneous for typical value of $p\approx 10^{100}$. – Jyrki Lahtonen Nov 01 '14 at 14:30