Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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)
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).
