# Wikipedia's double-and-add point multiplication algorithm for elliptical curves

Here's the algorithm Wikipedia gives for double-and-add point multiplication:

   N ← P
Q ← 0
for i from 0 to m do
if d[i] = 1 then
N ← point_double(N)
return Q


$P$ is an $(x, y)$ coordinate and so it seems reasonable to assume that $0$ is a $(0, 0)$ coordinate but there's no guarantee that $(0, 0)$ will even be on the curve, which would thus skew the whole thing.

Indeed, it seems to me that $Q$ is probably better represented as $\infty$ due to the P + ∞ = P identity?

I suppose one could assume that $0$ and $\infty$ are the same thing, but that wouldn't work if $(0, 0)$ were an actual point on the curve.

You are correct that $Q$ is initialized to the neutral element $\infty$ (or $\mathcal O$). Sometimes people use $0$ to represent the neutral element even though it may look ambiguous.

P is an x, y coordinate and so it seems reasonable to assume that 0 is a 0, 0 coordinate

Actually, that's an incorrect assumption; by 0, they really mean the point at infinity (aka the neutral element aka the identity element). That is, it is a point that doesn't actually correspond to a solution to the cubic equation, but instead is something that needs to be thrown in to make the curve a mathematical group.

As for how it is represented, well, that rather depends on the implementation; there might be implementations that represent it as (0, 0), but (as you point out), that might not work if $x=y=0$ is a valid solution to the equation.

• I guess one could represent with a zero denominator in projective coordinates. Jul 2 '17 at 17:15
• @CodesInChaos: yes, in projective coordinates, real implementations actually do that. I didn't want to complicate things too much, though... Jul 2 '17 at 17:19