Elliptic Curves
The Group Law on an Elliptic Curve
The chord-and-tangent addition law, its explicit formulas, and the coordinate systems that avoid inversion.
Engineering / MathematicsElliptic Curves2 min readKV-MATH-0635
The group law is defined geometrically by chords and tangents and computed by explicit rational formulas. Those formulas involve a division, which is what makes the law useful for factoring.
The geometric law
Three collinear points on the curve sum to the identity. To add two points, draw the line through them, find the third intersection, and reflect it in the horizontal axis.
Chord-and-tangent addition
- Draw the lineThrough the two points, or the tangent if they coincide.
- Find the third pointThe line meets the cubic in exactly three points counted properly.
- ReflectNegate the second coordinate to obtain the sum.
The formulas
The division
Avoiding inversion
| Coordinate system | Inversions per operation | Multiplications |
|---|---|---|
| Affine | One | Fewest |
| Projective | None | More |
| Jacobian | None | Fewer than plain projective for doubling |
| Montgomery form | None | Very efficient for scalar multiplication |
Scalar multiplication
Multiplying a point by an integer uses binary powering with doubling in place of squaring. Because negation is free on an elliptic curve, signed representations reduce the number of additions further.
Torsion and order
The order of a point divides the group order. For curves over finite fields the group order is near the field size by Hasse's theorem, and computing it exactly is the subject of Schoof's algorithm.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 7.1.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.