Elliptic-curve cryptography rests on two operations: adding two points, and “multiplying” a point PP by an integer kk. The security assumption is that kk cannot be recovered efficiently from PP and kPkP. That statement hides two separate questions. Why is point addition a group operation at all, associative, with an identity and inverses? And why is undoing the multiplication hard when the formulas involved are high-school algebra?

The formulas take a few lines to derive. After that, everything is checked on a curve over 𝔽17\mathbb{F}_{17} with exactly 19 points: small enough to do on paper, and small enough to test every case by machine. The last part is about what such a small example cannot tell you.

The curve and the point at infinity

Let KK be a field whose characteristic is neither 2 nor 3, and pick a,b∈Ka, b \in K with 4a3+27b2≠04a^3 + 27b^2 \neq 0. The elliptic curve

E:y2=x3+ax+bE:\; y^2 = x^3 + ax + b

consists of all solutions (x,y)∈K2(x, y) \in K^2 plus one extra point 𝒪\mathcal{O}. The condition on aa and bb means that x3+ax+bx^3 + ax + b has no repeated root, so the curve has no cusp and no self-intersection, and every point has a unique tangent line. The curve y2=x3y^2 = x^3 violates it: it has a cusp at the origin, and the tangent construction below breaks down there.

𝒪\mathcal{O} comes from projective geometry. Written homogeneously, the equation is Y2Z=X3+aXZ2+bZ3Y^2 Z = X^3 + aXZ^2 + bZ^3. Setting Z=0Z = 0 forces X=0X = 0, which leaves the single point [0:1:0][0 : 1 : 0]. Every vertical line passes through it.

Chords and tangents

Over the reals, addition has a picture. The line through two points PP and QQ on the curve meets it in a third point RR, and P+QP + Q is defined as the reflection of RR in the xx-axis.

Adding two points on an elliptic curve The real curve y² = x³ − 2x + 2. A line through P = (−1, √3) and Q = (1, 1) meets the curve in a third point R. Its mirror image in the x-axis is P + Q. P Q R P + Q
A chord through P and Q on the real curve y² = x³ − 2x + 2: the third intersection R, mirrored in the x-axis, is P + Q.

The useful fact is that RR can be computed without taking any roots. Take P=(x1,y1)P = (x_1, y_1) and Q=(x2,y2)Q = (x_2, y_2) with x1≠x2x_1 \neq x_2, and the line y=λx+νy = \lambda x + \nu through both:

λ=y2−y1x2−x1,ν=y1−λx1.\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \qquad \nu = y_1 - \lambda x_1 .

Substituting it into the curve equation and collecting terms gives a monic cubic,

x3−λ2x2+(a−2λν)x+(b−ν2)=0,x^3 - \lambda^2 x^2 + (a - 2\lambda\nu)\,x + (b - \nu^2) = 0 ,

two of whose roots, x1x_1 and x2x_2, are already known. By Vieta’s formulas the three roots add up to minus the x2x^2 coefficient, so x1+x2+x3=λ2x_1 + x_2 + x_3 = \lambda^2 and

x3=λ2−x1−x2.x_3 = \lambda^2 - x_1 - x_2 .

R=(x3,λx3+ν)R = (x_3, \lambda x_3 + \nu) lies on the line. Reflecting flips the sign of the second coordinate, and substituting ν\nu gives

P+Q=(x3,y3),y3=λ(x1−x3)−y1.P + Q = (x_3, y_3), \qquad y_3 = \lambda (x_1 - x_3) - y_1 .

Only field operations appear, so the same formulas work over any field, including 𝔽p\mathbb{F}_p, where there is nothing left to draw.

The remaining cases:

  • Doubling, P=QP = Q: the chord becomes the tangent. Differentiating implicitly, 2yy′=3x2+a2y\,y' = 3x^2 + a, so λ=(3x12+a)/(2y1)\lambda = (3x_1^2 + a)/(2y_1). The point of contact is a double root, which gives x3=λ2−2x1x_3 = \lambda^2 - 2x_1; the formula for y3y_3 is unchanged.
  • x1=x2x_1 = x_2, y1=−y2y_1 = -y_2: the line is vertical and its third intersection is 𝒪\mathcal{O}, so P+Q=𝒪P + Q = \mathcal{O}. This includes doubling a point with y1=0y_1 = 0, whose tangent is vertical.
  • 𝒪\mathcal{O} as a summand: P+𝒪=PP + \mathcal{O} = P.

Which axioms are easy

Closure, identity, inverses and commutativity are immediate. 𝒪\mathcal{O} is the identity. The inverse of (x,y)(x, y) is (x,−y)(x, -y), because the line through the two is vertical. The line through PP and QQ is the line through QQ and PP, so the operation is commutative. And the formulas produce coordinates in KK that satisfy the curve equation by construction.

Associativity is a different matter. Nothing in the picture suggests that (P+Q)+R=P+(Q+R)(P + Q) + R = P + (Q + R), and none of the known proofs is short. Washington gives a fairly elementary one in Section 2.4 of his book. Silverman derives it in Chapter III from the Riemann–Roch theorem: the map P↦(P)−(𝒪)P \mapsto (P) - (\mathcal{O}) identifies the points with the group of degree-zero divisor classes, whose operation is associative for free. If you only know the group law through its formulas, it is worth knowing that this is where the work is hidden.

What a small curve allows instead is brute force: check every triple. That proves nothing about other curves, but it is very good at catching mistakes, as the end of this post shows.

A curve with 19 points

The curve

E:y2=x3+2x+2over 𝔽17E:\; y^2 = x^3 + 2x + 2 \quad \text{over } \mathbb{F}_{17}

is a standard textbook example; Paar and Pelzl use it in Chapter 9. The non-singularity condition holds, since 4⋅23+27⋅22=140≡4(mod17)4 \cdot 2^3 + 27 \cdot 2^2 = 140 \equiv 4 \pmod{17}.

To list its points, test for each xx from 0 to 16 whether x3+2x+2x^3 + 2x + 2 is a square modulo 17. Nine values of xx qualify, each with two square roots ±y\pm y, which gives 18 points, plus 𝒪\mathcal{O}:

x035679101316
y6, 111, 161, 163, 146, 111, 166, 117, 104, 13

Hasse’s theorem bounds the count by |#E(𝔽p)−(p+1)|≤2p|\#E(\mathbb{F}_p) - (p + 1)| \le 2\sqrt{p}, which here means somewhere between about 9.75 and 26.25. Since 19 is prime, Lagrange’s theorem does the rest: every point other than 𝒪\mathcal{O} has order 19, so the group is cyclic and any such point generates it.

Doubling P=(5,1)P = (5, 1). Division now means multiplying by an inverse mod 17. The tangent slope is λ=(3⋅25+2)⋅2−1\lambda = (3 \cdot 25 + 2) \cdot 2^{-1}. Here 77≡977 \equiv 9 and 2−1≡92^{-1} \equiv 9 (because 2⋅9=18≡12 \cdot 9 = 18 \equiv 1), so λ≡81≡13\lambda \equiv 81 \equiv 13, and

x3=132−2⋅5=159≡6,x_3 = 13^2 - 2 \cdot 5 = 159 \equiv 6,
y3=13⋅(5−6)−1=−14≡3.y_3 = 13 \cdot (5 - 6) - 1 = -14 \equiv 3 .

So 2P=(6,3)2P = (6, 3). To check: 32=93^2 = 9, and 63+12+2=230=13⋅17+96^3 + 12 + 2 = 230 = 13 \cdot 17 + 9.

Adding PP and 2P2P. The chord slope is λ=(3−1)/(6−5)=2\lambda = (3 - 1)/(6 - 5) = 2, so x3=4−5−6≡10x_3 = 4 - 5 - 6 \equiv 10 and y3=2⋅(5−10)−1≡6y_3 = 2 \cdot (5 - 10) - 1 \equiv 6, that is, 3P=(10,6)3P = (10, 6). Carrying on gives all multiples up to 19P=𝒪19P = \mathcal{O}, here in pairs:

kkP19 − k(19 − k)P
1(5, 1)18(5, 16)
2(6, 3)17(6, 14)
3(10, 6)16(10, 11)
4(3, 1)15(3, 16)
5(9, 16)14(9, 1)
6(16, 13)13(16, 4)
7(0, 6)12(0, 11)
8(13, 7)11(13, 10)
9(7, 6)10(7, 11)

The pairing shows the only visible regularity: kPkP and (19−k)P=−kP(19 - k)P = -kP share their xx-coordinate. Down the columns, the coordinates follow no pattern.

Fast in one direction

Nobody computes kPkP with k−1k - 1 additions. Double-and-add walks through the bits of kk from the top: double at every bit, add PP when the bit is

  1. For k=13=11012k = 13 = 1101_2 the intermediate results are PP, then 2P2P and 3P3P, then 6P6P, then 12P12P and 13P=(16,4)13P = (16, 4). An ℓ\ell-bit scalar costs ℓ−1\ell - 1 doublings and at most ℓ−1\ell - 1 additions, so about 510 group operations for a 256-bit kk.

The other direction

Given PP and Q=kPQ = kP, find kk. For Q=(13,7)Q = (13, 7) the table says k=8k = 8. With 19 points, looking it up is the whole algorithm. The real question is how the cost grows with the group order nn.

Baby-step giant-step (Shanks) writes k=im+jk = im + j with m=⌈n⌉m = \lceil \sqrt{n} \rceil, stores the baby steps jPjP for 0≤j<m0 \le j < m, and walks with giant steps Q,Q−mP,Q−2mP,…Q, Q - mP, Q - 2mP, \dots until it lands on a stored point. Here m=5m = 5, the stored points are 𝒪,(5,1),(6,3),(10,6),(3,1)\mathcal{O}, (5, 1), (6, 3), (10, 6), (3, 1), and −5P=(9,1)-5P = (9, 1). The first giant step, (13,7)(13, 7), is not stored; the second, (13,7)+(9,1)=(10,6)(13, 7) + (9, 1) = (10, 6), is the baby step j=3j = 3. Hence k=1⋅5+3=8k = 1 \cdot 5 + 3 = 8.

Both time and memory grow like n\sqrt{n}. Pollard’s rho method (1978) needs about the same number of steps, on average roughly πn/4\sqrt{\pi n / 4}, with constant memory.

Why nothing much better is known. Shoup proved in 1997 that any generic algorithm, one that uses only group operations and ignores how elements are encoded, needs Ω(p)\Omega(\sqrt{p}) group operations, where pp is the largest prime factor of the group order. In that model, baby-step giant-step and rho are optimal. In 𝔽p×\mathbb{F}_p^\times, index calculus beats the bound by exploiting the fact that integers factor into small primes. For points on a general elliptic curve over a prime field, no comparable notion is known, and neither is an algorithm that does substantially better than n\sqrt{n}.

For scale: secp256k1, the curve Bitcoin uses, is y2=x3+7y^2 = x^3 + 7 over the prime field with p=2256−232−977p = 2^{256} - 2^{32} - 977. Its group order is a prime just below 22562^{256} (cofactor 1), so rho needs about πn/4≈2127.8\sqrt{\pi n / 4} \approx 2^{127.8} group operations.

Where intuition misleads

Simple formulas, simple inversion. The addition formulas are easy to invert: given P+QP + Q and PP, subtracting gives QQ. What is hard is counting how many times PP was added, and the formulas say nothing about that. Its hardness is an assumption, not a theorem. Shoup’s bound covers generic algorithms only, and the toy table is no evidence at all, since every problem with 19 elements is easy.

Large group, secure group. What matters is the largest prime factor of the group order. If nn splits into small primes, the Pohlig–Hellman method reduces the logarithm to logarithms in the small subgroups, and the cost is set by the largest factor. That is why curves in use have prime order or a tiny cofactor.

Prime order is enough. It is not. If #E(𝔽p)=p\#E(\mathbb{F}_p) = p (an anomalous curve), Smart’s 1999 method solves the logarithm in polynomial time. If the embedding degree, the smallest BB with pB≡1(modn)p^B \equiv 1 \pmod n, is small, the MOV attack of Menezes, Okamoto and Vanstone moves the problem into 𝔽pB×\mathbb{F}_{p^B}^\times, where index calculus applies. SEC 1 therefore requires, when validating curve parameters, that pB≢1(modn)p^B \not\equiv 1 \pmod n for all 1≤B<1001 \le B < 100 and that n≠pn \neq p. The toy curve fails this independently of its size: 179≡1(mod19)17^9 \equiv 1 \pmod{19}, so its embedding degree is 9. secp256k1 passes.

Correct maths, correct code. The case distinctions (P=QP = Q, P=−QP = -Q, 𝒪\mathcal{O}) are a known source of bugs. Double-and-add has a second problem: whether an addition happens depends on a bit of the secret scalar, which can show up in timing or power consumption. Implementations therefore use fixed operation sequences such as the Montgomery ladder, which RFC 7748 specifies for X25519, or complete addition formulas without special cases, such as those Renes, Costello and Batina give for prime-order curves.

Checking it by machine

This program contains everything above: addition with all cases, double-and-add, point counting, an exhaustive test of the group axioms, and baby-step giant-step.

from math import isqrt

p, a, b = 17, 2, 2
O = None  # point at infinity

def on_curve(P):
    return P is O or (P[1] ** 2 - (P[0] ** 3 + a * P[0] + b)) % p == 0

def neg(P):
    return O if P is O else (P[0], -P[1] % p)

def add(P, Q):
    if P is O: return Q
    if Q is O: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return O                                  # P + (-P)
    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
    return (x3, (lam * (x1 - x3) - y1) % p)

def mul(k, P):                                    # double-and-add
    R = O
    for bit in bin(k)[2:]:
        R = add(R, R)
        if bit == "1":
            R = add(R, P)
    return R

points = [O] + [(x, y) for x in range(p) for y in range(p) if on_curve((x, y))]
assert len(points) == 19

for P in points:                                  # identity, inverse, commutative
    assert add(P, O) == P and add(P, neg(P)) is O
    for Q in points:
        assert add(P, Q) == add(Q, P) and on_curve(add(P, Q))
        for R in points:                          # associative: 19³ = 6859 triples
            assert add(add(P, Q), R) == add(P, add(Q, R))

G, Q = (5, 1), (13, 7)
assert mul(2, G) == (6, 3) and mul(3, G) == (10, 6) and mul(19, G) is O

m = isqrt(len(points) - 1) + 1                    # ⌈√19⌉ = 5
baby = {mul(j, G): j for j in range(m)}
giant, step = Q, neg(mul(m, G))
for i in range(m):
    if giant in baby:
        print("log =", i * m + baby[giant])       # log = 8
        break
    giant = add(giant, step)

The exhaustive test earns its keep. Drop the factor 2 from the tangent slope, and all 18 doublings land off the curve while 1152 of the 6859 triples violate associativity. Return the third intersection RR instead of −R-R, and 𝒪\mathcal{O} stops being the identity for every point on the curve, with 6498 failing triples. Neither mistake shows up if you only check a few examples by hand that were produced with the same wrong formula.

Further reading