Associativity 2
Associativity is a fundamental property for the arithmetic of points on an elliptic curve, ensuring that for any three points P, Q, and R on the curve, the equation (P + Q) + R = P + (Q + R) always holds.
Associativity is a fundamental property for the arithmetic of points on an elliptic curve, ensuring that for any three points P, Q, and R on the curve, the equation (P + Q) + R = P + (Q + R) always holds. Demonstrating this property involves both geometric intuition and algebraic verification. Here’s a conceptual argument for the associativity of addition on an elliptic curves:
Geometric Intuition
Looking at the image on this page: (P + Q) + R = the point at infinity, and (P + R) + Q = the point at infinity, and (Q + R) + P = the point at infinity.
1. Initial Setup: Consider three points P, Q, and R on an elliptic curve. The addition of these points involves drawing lines through pairs of points and finding intersections with the curve, as per the curve's addition rules. See image attached.
2. Calculate P + Q: First, add P and Q by drawing a line through these points. The line intersects the curve at a third point, which is reflected over the x-axis to get P + Q.
3. Add R to the Result: Next, add R to P + Q by drawing a line through R and the result of P + Q, finding where it intersects the curve, and reflecting this new intersection point over the x-axis.
4. Calculate Q + R: Similarly, add Q and R by drawing a line through Q and R, intersecting the curve, and reflecting the point to find Q + R.
5. Add P to the Result: Finally, add P to the result of Q + R using the same geometric process.
In both paths (P + Q) + R and P + (Q + R), the final step involves drawing a line through the intermediate sum and the remaining point, intersecting the curve, and reflecting the point. Geometrically, because of the symmetry and the smoothness of the curve, these operations will converge to the same result, illustrating the associativity of addition on the curve.
Algebraic Verification
Algebraically, associativity can be verified by using the explicit formulas for point addition on an elliptic curve. These formulas involve the coordinates of the points and the slope of the line connecting them (or the tangent line, in the case of doubling a point).
1. Slope Calculations: For P + Q, one calculates the slope m_PQ between P and Q. Similarly, for Q + R, calculate the slope m_QR.
2. Point Calculations: Using m_PQ, find P + Q, and with m_QR, find Q + R.
3. Repeat Process: To find (P + Q) + R, calculate the slope between P + Q and R, and similarly for P + Q + R.
Through algebraic manipulation, one can show that both paths yield the same x and y coordinates for the final sum, relying on the curve's equation and the distributive, commutative, and associative properties of real number arithmetic. This rigorous algebraic proof is based on the explicit formulas for point addition and the properties of the field over which the elliptic curve is defined.
Conclusion
The associativity of point addition on an elliptic curve is not immediately obvious and requires careful proof. While geometric intuition provides a visual understanding, algebraic verification through the elliptic curve equations and addition formulas confirms associativity beyond any geometric ambiguity. This property is crucial for the mathematical structure that makes elliptic curves suitable for complex applications like cryptography, where the reliability of operations underpins security protocols.