These notes continue the bignum arithmetic series. The bignum layer defines 32-bit words, radix \(B=2^{32}\), half-word product decomposition, Montgomery reduction, canonicalization, and constant-time C idioms. The elliptic layer uses that substrate to implement the group law on a curve over a finite field.

The reference spine is Hankerson, Menezes, and Vanstone, Guide to Elliptic Curve Cryptography: finite-field arithmetic in Chapter 2, point formulas and scalar multiplication in Chapter 3, domain-parameter and protocol checks in Chapter 4, and implementation/security issues in Chapter 5.

Coverage audit

This series is deliberately prime-field first. Binary-field and Koblitz material from the book is noted where it changes the algorithmic tradeoff, but the C library target is a short-Weierstrass prime-field implementation.

Library boundary

For a fixed curve over \(\mathbb F_p\),

the arithmetic layer should expose:

1. field operations on canonical or explicitly lazy residues;
2. affine and Jacobian point representations;
3. point validation and subgroup-related checks for public data;
4. scalar multiplication routines whose control flow is independent of secret scalar bits.

The layer should not pretend to implement ECDSA or ECDH by itself. Protocols still determine nonce generation, transcript binding, key derivation, signature encoding, and invalid-input handling.

Two concrete running examples

Toy curve for exact inspection. Over \(\mathbb F_{17}\), the curve

is nonsingular because \(4\cdot 2^3+27\cdot 2^2=140\equiv 4\pmod {17}\). Small-field examples make every exceptional case visible: infinity, inverses, doubling with \(y=0\), and points that are not on the curve.

Implementation-scale prime. The teaching and implementation-test model for P-256 represents a 256-bit field element as eight little-endian uint32_t words with \(B=2^{32}\). Every 32-by-32 product is decomposed into 16-bit partial products before carry propagation. The elliptic formulas see only the field API, but the field proof must match this word representation.

SageMath as oracle

SageMath supplies exact algebra and test vectors. It does not prove C behavior: C still needs word-size bounds, no signed overflow, and constant-time review.

p = 17
F = GF(p)
E = EllipticCurve(F, [2, 2])
P = E(5, 1)
print(E.discriminant() != 0)
print(2*P)
print(19*P == 0*P)

Article route