2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Nov 1 '14 at 14:33
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MBrown Oct 28 '14 at 11:49
  • $\begingroup$ 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}$. $\endgroup$ – Jyrki Lahtonen Nov 1 '14 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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