Elliptic-curve arithmetic turns points on a cubic equation into a finite abelian group where addition is geometric in origin, algebraic in execution and computationally efficient.
Over the real numbers, an elliptic curve can be drawn as a smooth cubic. Over a finite field, the picture becomes a finite set of residue pairs. Yet the same group law survives: two points can be added, a point can be doubled, and repeated addition creates scalar multiplication.
This guide develops the computational Mathematics of curves over prime fields. The focus is the group law, exact modular formulas, edge cases, scalar multiplication, point order and the connection to the discrete logarithm problem.
This is Guide 8 in the Bukit Timah Tutor Computational Number Theory series. Use the BTT Mathematics Hub for the wider Mathematics route.
Curve equation → finite point set → group law → scalar multiplication → order structure → verification.
1. The short Weierstrass form
Over a field of characteristic not 2 or 3, a common elliptic-curve model is
E: y²=x³+ax+b.
Over the prime field F_p, x,y,a,b are residues modulo p and the equation is interpreted modulo p.
The curve must be nonsingular. For the short Weierstrass form this requires
4a³+27b² not congruent to 0 (mod p).
If this expression vanished, the cubic would have a singular point and the standard elliptic-curve group law would break down.
2. A working example over F97
Consider
E: y²=x³+2x+3 (mod 97).
Here 4a³+27b²=4·8+27·9=275≡81 (mod 97), which is nonzero. The curve is nonsingular.
The point P=(3,6) lies on E because
6² = 36 3³+2·3+3 = 27+6+3 = 36.
So the two sides agree modulo 97.
3. The point at infinity
The affine points alone do not form a group. One additional formal point, usually written O, is included and acts as the identity:
P+O=O+P=P.
Geometrically O can be understood through the projective completion of the cubic. Computationally it behaves as a distinguished identity state.
4. Negating a point
If P=(x,y), then
−P=(x,−y mod p).
Both points lie on the curve because y²=(−y)². Their sum is O.
For P=(3,6) on the example curve, −P=(3,91) because −6≡91 (mod 97).
5. Point addition
Let P=(x1,y1) and Q=(x2,y2) be distinct points with x1≠x2. Define the slope
m=(y2−y1)(x2−x1)⁻¹ mod p.
Then R=P+Q=(x3,y3) is given by
x3 = m² − x1 − x2 mod p y3 = m(x1−x3) − y1 mod p.
The division in the slope is modular division, so it means multiplication by a modular inverse. Over a prime field every nonzero denominator is invertible.
6. Why the formulas come from a line
Over the reals, the line through P and Q intersects a nonsingular cubic in a third point. Reflecting that third intersection across the x-axis defines the group sum.
Algebraically, substitute the line equation into the cubic. The resulting cubic polynomial in x has the known roots x1 and x2, and Vieta’s relations identify the third root. The modular formulas are the finite-field version of the same algebra.
7. Point doubling
When Q=P, the secant slope becomes a tangent slope. If y1≠0,
m=(3×1²+a)(2y1)⁻¹ mod p.
Then the same coordinate formulas give 2P.
If y1=0, the tangent is vertical and P=−P, so 2P=O.
8. Worked doubling: P=(3,6)
On E:y²=x³+2x+3 mod 97,
m = (3·3²+2)/(2·6) = 29/12 mod 97.
The inverse of 12 modulo 97 is 89 because 12·89=1068≡1. Hence
m ≡ 29·89 ≡ 59 (mod 97). x3 ≡ 59²−3−3 ≡ 80. y3 ≡ 59(3−80)−6 ≡ 10.
Therefore
2P=(80,10).
Verification: 10²=100≡3, while 80³+2·80+3≡3 (mod 97).
9. Continuing the example
Add P=(3,6) to 2P=(80,10). The result is
3P=(80,87).
Notice that (80,87)=−(80,10), so 3P=−2P. Adding P again gives 4P=(3,91)=−P, and therefore 5P=O.
The point P has order 5.
10. Group axioms
The points of a nonsingular elliptic curve over a field, together with O, form an abelian group.
- Closure: P+Q is another curve point or O.
- Identity: P+O=P.
- Inverse: P+(−P)=O.
- Commutativity: P+Q=Q+P.
- Associativity: (P+Q)+R=P+(Q+R).
Associativity is the least obvious property from the elementary formulas. It follows from the deeper algebraic geometry of the cubic, not from a simple visual argument alone.
11. Edge cases in point addition
- If P=O, return Q.
- If Q=O, return P.
- If x1=x2 and y1≡−y2, return O.
- If P=Q and y1=0, return O.
- Otherwise use the addition or doubling slope.
Explicit handling of these cases prevents attempted inversion of zero.
12. Scalar multiplication
For an integer k≥0, scalar multiplication means repeated addition:
kP=P+P+…+P (k copies).
Naively this takes O(k) additions. The better method copies binary exponentiation: repeatedly double the current point and add selected powers according to the binary digits of k.
13. Double-and-add
scalar_multiply(k,P): R = O Q = P while k > 0: if k is odd: R = R + Q Q = 2Q k = floor(k/2) return RThe loop consumes one binary digit at a time, so scalar multiplication uses O(log k) point doublings and additions.
14. The invariant behind double-and-add
If the original target is k0P, maintain
R+kQ=k0P.
When k is odd, move one copy of Q into R. Then double Q while halving the remaining k. The represented group element does not change. When k reaches zero, R is the desired scalar multiple.
15. Negative scalars
For k<0, define kP=(−k)(−P). Since negating a point is inexpensive, algorithms can normalise the sign first and run ordinary scalar multiplication on |k|.
16. Point order
The order of P is the least positive r such that rP=O. It divides the total number of points #E(F_p) by Lagrange’s theorem.
If the group order is known and factored, the order of P can be reduced efficiently. Start with r=#E and test whether (r/q)P=O for prime factors q of r. Whenever the test succeeds, divide r by q and continue.
17. Counting points
For a small prime p, point counting can be done directly. For each x, compute the right-hand side x³+ax+b and determine whether it is a quadratic residue. A nonzero residue contributes two y-values, zero contributes one, and a nonresidue contributes none. Add the point O at the end.
For the example curve over F97, the total is
#E(F97)=100.
The example point P has order 5, which divides 100 as required.
18. Hasse’s bound
Hasse’s theorem constrains the number of points:
|#E(F_p)−(p+1)|≤2√p.
For p=97, the centre is 98 and the example count is 100, comfortably within the allowed interval.
Hasse’s bound is important because it says an elliptic-curve group over F_p has size roughly p, while allowing enough variation for different curves to have different group structures.
19. Point counting is a computational problem
Directly testing every x is O(p) field-scale work and becomes unsuitable for huge p. Sophisticated point-counting algorithms exploit Frobenius endomorphisms and algebraic structure to determine #E(F_p) much more efficiently.
The conceptual lesson is familiar: a definition gives one algorithm, but deeper structure can produce a much faster one.
20. Elliptic-curve discrete logarithms
In an elliptic-curve group, the discrete logarithm problem is written additively. Given points P and Q in the subgroup generated by P, find x such that
Q=xP.
The generic algorithms from Guide 6 transfer directly. Baby-step giant-step stores point multiples. Pollard rho constructs a pseudorandom walk among linear combinations aP+bQ and converts a collision into a linear congruence for x.
This is a powerful example of abstraction: the algorithms do not require ordinary multiplication of residues. They require only a finite group operation, inverses and equality.
21. Why group structure matters
The full point group E(F_p) need not be cyclic, although it is always a finite abelian group with restricted structure. Computations often take place inside a cyclic subgroup generated by a chosen point P.
The actual order r=ord(P) controls scalar periodicity and the corresponding discrete-logarithm search space. As before, the ambient group size and the element order should not be confused.
22. Coordinate representations
The affine formulas shown above require a modular inversion in each general addition or doubling. Inversion can be substantially more expensive than multiplication.
Projective coordinate systems introduce extra coordinates so many group operations can be performed using multiplications and squarings instead of immediate inversion. One final inversion converts the result back to affine coordinates.
This illustrates a broader computational tradeoff: change representation to make the common operation cheaper, then pay conversion cost only when needed.
23. Exact implementation discipline
- Reduce field coordinates modulo p after arithmetic.
- Check denominators before inversion.
- Represent O explicitly rather than inventing ordinary coordinates for it.
- Validate that input points lie on the curve when the context requires it.
- Use exact modular inversion, not floating-point division.
- Preserve the curve parameters and field modulus consistently across all operations.
24. Common mistakes
- Using a singular cubic. Check the discriminant condition first.
- Dividing as real numbers. Slopes require modular inverses.
- Forgetting P+(−P)=O. A zero denominator here signals the identity case, not a failed inverse routine.
- Using the distinct-point slope for doubling. Doubling has a different numerator and denominator.
- Confusing scalar multiplication with coordinate multiplication. kP means repeated group addition.
- Using O(k) repeated addition for a large scalar. Use double-and-add.
- Assuming every point has order #E. Point order only has to divide #E.
25. Practice set
- Check that E:y²=x³+2x+3 is nonsingular modulo 97.
- Verify that P=(3,6) lies on E.
- Find −P.
- Find the inverse of 12 modulo 97.
- Use the doubling formula to compute 2P.
- Verify that 2P lies on E.
- Given 3P=(80,87), explain why 3P=−2P.
- Use the sequence P,2P,3P,4P,5P to determine ord(P).
- Explain why double-and-add uses O(log k) loop iterations.
- State Hasse’s bound.
- Why must ord(P) divide #E(F_p)?
- Translate the multiplicative discrete-log equation g^x=h into elliptic-curve additive notation.
26. Answers and checks
1. 4·2³+27·3²=275≡81 (mod 97), nonzero.
2. 6²=36 and 3³+2·3+3=36.
3. −P=(3,91).
4. 12⁻¹≡89 (mod 97).
5. The slope is 59 and 2P=(80,10).
6. 10²≡3 and 80³+2·80+3≡3 (mod 97).
7. The points have the same x-coordinate and y-values 10 and 87 with 10+87=97, so they are negatives.
8. 5P=O and no smaller positive multiple is O, so ord(P)=5.
9. Each iteration halves the remaining scalar, consuming one binary digit.
10. |#E(F_p)−(p+1)|≤2√p.
11. The subgroup generated by P is a subgroup of the finite group E(F_p), so Lagrange’s theorem applies.
12. Given P and Q, find x such that Q=xP.
27. What Batch 02 adds to the estate
The second four-guide batch pushes computational number theory beyond basic modular arithmetic into richer algebraic structures.
- Quadratic residues turn square-root existence into symbol arithmetic and root-finding algorithms.
- Discrete logarithms expose the complexity of reversing efficient group exponentiation.
- Continued fractions turn Euclidean quotients into best approximations and Pell solutions.
- Elliptic curves build a new finite group where the same ideas of order, scalar multiplication and discrete logarithms reappear.
The subject grows not by abandoning earlier algorithms, but by reusing them inside new structures.
28. Computational Number Theory — Batch 02
- Guide 5: Quadratic Residues, Legendre & Jacobi Symbols and Tonelli–Shanks
- Guide 6: Discrete Logarithms, Baby-Step Giant-Step and Pollard Rho
- Guide 7: Continued Fractions, Convergents and Pell Equations
- Guide 8: Elliptic Curves over Finite Fields, Point Arithmetic and Scalar Multiplication
Return to the Singapore Mathematics Hub for the complete public Mathematics estate.