1
$\begingroup$

This may be more of a math question but I cannot find an intuitive answer.

On an EC curve why is 2P+2P equal to P+P+P+P?

The addition operation seems to a layman as some arbitrary sequence of steps. Draw a line here, flip the y coordinate, and so on. And yet point doubling twice brings up the same point. How is this so? (how is it that point addition is associative)

$\endgroup$
8
  • $\begingroup$ Scalar multiplication. Doubling brings up the same point? Not clear. See the Group Law where we have that the group law has a geometric maning. Hard to find one dupe! $\endgroup$
    – kelalaka
    Oct 26 '21 at 21:10
  • $\begingroup$ If those answer doesn't resolve your points, please indicate. $\endgroup$
    – kelalaka
    Oct 26 '21 at 21:26
  • $\begingroup$ @kelaka ok it points me in the right direction. I need to look into 'groups'. Still i cannot yet understand how this seemingly arbitrary operation was created that 2P added yields the same as P added 4 times $\endgroup$
    – Frank
    Oct 27 '21 at 3:44
  • $\begingroup$ In other words, how is it that that operation is associative? $\endgroup$
    – Frank
    Oct 27 '21 at 3:47
  • 1
    $\begingroup$ Also, you might be interested in the Elliptic Tales as a gentle introduction. And one of the many answers from math.se; Group Law for an Elliptic curve $\endgroup$
    – kelalaka
    Oct 27 '21 at 10:34
4
$\begingroup$

There do exist proofs of the associativity of the elliptic curve group law based on the geometric definition (together with some results in projective geometry), but they are definitely non trivial. Cassels' little book on elliptic curves contains such a proof (and it's a nice introduction to the theory of elliptic curves in general, so I would definitely recommend it).

The most elementary way of proving associativity is of course to just write down the coefficients for $(P+Q)+R$ and $P+(Q+R)$ and observe that they are the same, but I certainly agree that this doesn't explain anything.

There are more highbrow approaches that explain the reason why the addition law looks like that, but they require more math. The underlying argument goes like this: there is an additive group associated to any algebraic curve called the group of degree-zero divisors, and it is actually a group “variety” in the sense that it can be represented by a geometric object (called the Jacobian variety) with the group operations given by geometric maps. Moreover, the dimension of that geometric object turns one to be the genus, a number which is $1$ exactly for elliptic curves, or more properly, for things that become elliptic curves once you fix a distinguished point. And once you fix that distinguished point, there is a simple way to map any point on the curve to a degree-zero divisor. This gives you a map between the original curve and the Jacobian, which turns out to be an isomorphism, and so the group law on the original elliptic curve comes from the natural group law on the Jacobian, for which all the group properties hold trivially. Due to how divisors behave, it is also easy to see that three points sum to zero if and only if they are on a line, so you recover the traditional geometric description.

Making the above entirely rigorous requires a good amount of algebraic geometry machinery, but it is in some sense the correct way to see where associativity comes from. (Historically, things came about differently, via analytic methods that extended the addition laws from trigonometric functions to so-called elliptic functions, but that historical way doesn't map very well to the finite field setting that we use in cryptography).

$\endgroup$
2
  • $\begingroup$ Many thanks Mehdi. Well I now have a rabbit hole of maths to dive into that was created by a dinosaur sized rabbit, but at least i now know that it is the correct rabbit! $\endgroup$
    – Frank
    Oct 27 '21 at 8:03
  • $\begingroup$ Book ordered! 👍 $\endgroup$
    – Frank
    Oct 27 '21 at 8:22

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.