1
$\begingroup$

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
          Q ← point_add(Q, N)
      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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.