THE GARDEN

Elliptic Curves (Group Law Basics)

Updated 13 Sep 2026

• •

  What it is

  • •

    An elliptic curve over a field is the set of points $(x,y)$ satisfying an equation of the form $y^2 = x^3 + ax + b$ (a smooth cubic — no repeated roots, checked via a nonzero discriminant), plus one extra "point at infinity" that serves as the group identity. Remarkably, these points form a genuine abelian group under a geometrically-defined addition: to add two points $P$ and $Q$, draw the line through them, find its third intersection with the curve, and reflect that point across the x-axis to get $P+Q$ (doubling a point uses the tangent line instead). This group operation has no efficient "logarithm" — no known fast way, in general, to recover $k$ from a point $P$ and $kP$ — which is the entire basis of elliptic curve cryptography (ECDH, ECDSA). Crucially, this hardness is a property of a genuine cubic curve specifically; equations that only look similar (conics, singular curves, curves over the wrong kind of ring) can secretly be isomorphic to a much simpler, easily-solved group instead.

• •

  When to apply

  • •

    Any protocol described as "elliptic curve" based — but always verify the actual group law and curve equation match the real thing, since "elliptic-curve-flavored" code that's actually built on a different underlying object (a conic, for instance) doesn't inherit real ECC's hardness at all.

• •

  Symbols and assumptions

  • •

    Work on $E:y^2=x^3+ax+b$ over $\mathbb F_p$, with prime $p>3$ and $4a^3+27b^2\not\equiv0$. Points include an identity $\mathcal O$. All coordinate arithmetic, including inverses, is modulo $p$.

• •

  Math — step by step

  • •
    1. Negation is $-(x,y)=(x,-y\bmod p)$. Thus $P+(-P)=\mathcal O$. Handle this vertical-line case before trying to divide by zero.
  • •
    2. For distinct non-opposite points use slope $\lambda=(y_2-y_1)(x_2-x_1)^{-1}$. For doubling with $y_1\ne0$, use $\lambda=(3x_1^2+a)(2y_1)^{-1}$. Doubling a point with $y=0$ gives $\mathcal O$.
  • •
    3. The line meets the cubic at a third point; reflecting its y-coordinate gives the sum: $x_3=\lambda^2-x_1-x_2$ and $y_3=\lambda(x_1-x_3)-y_1$. Reduce each result modulo $p$.
  • •
    4. Scalar multiplication $kP$ means repeated point addition, efficiently evaluated by doubling and adding. It is not coordinate-wise multiplication.
• •

  Worked example

  • •

    On $y^2=x^3+2x+2\pmod{17}$ take $P=(5,1)$. Check membership: $1^2\equiv125+10+2=137\equiv1$. The discriminant expression is $4\cdot8+27\cdot4=140\equiv4\ne0$.

  • •

    Double $P$: numerator $3\cdot25+2=77\equiv9$; denominator $2$ has inverse 9. Hence $\lambda=9\cdot9\bmod17=13$. Then $x_3=169-10\equiv6$, $y_3=13(5-6)-1=-14\equiv3$. So $2P=(6,3)$.

  • •

    Add $P+2P$: $\lambda=(3-1)/(6-5)=2$; $x_3=4-5-6\equiv10$; $y_3=2(5-10)-1\equiv6$. Thus $3P=(10,6)$. Check: $6^2\equiv2$ and $10^3+20+2\equiv2$.

• •

  Python

  • •

    def point_add(P, Q, a, p):
            if P is None: return Q
            if Q is None: return P
            x1, y1 = P; x2, y2 = Q
            if x1 == x2 and (y1 + y2) % p == 0:
                return None  # point at infinity
            if P == Q:
                lam = (3*x1*x1 + a) * pow(2*y1, -1, p) % p
            else:
                lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
            x3 = (lam*lam - x1 - x2) % p
            y3 = (lam*(x1 - x3) - y1) % p
            return (x3, y3)
     
    def scalar_mult(P, k, a, p):
            R = None
            while k > 0:
                if k & 1: R = point_add(R, P, a, p)
                P = point_add(P, P, a, p)
                k >>= 1
            return R
    

• •

  SageMath

  • •

    E = EllipticCurve(GF(p), [a, b])
    G = E.random_point()
    kG = k * G   # scalar multiplication via the * operator, group law handled automatically
    

• •

  Related

  • •

    Groups (Group Theory Basics)

  • •

    Discrete Logarithm Problem (DLP)

  • •

    Conic-Non-Elliptic Curve DLP Reduction (Fake ECC)

• •

  Cards

  • •

    What geometric operation defines addition of two points on an elliptic curve?

    • •

      Draw the line through the two points, find its third intersection with the curve, and reflect across the x-axis.

  • •

    What condition on a curve's coefficients guarantees it's a genuine (non-singular) elliptic curve?

    • •

      The discriminant 4a³+27b² must be nonzero (mod the field's characteristic) — a zero discriminant means the curve has a singular point, breaking the group law.

◌ Explore connections in Graph view