Curves over Finite Fields

Cryptography · Axiom Academy

LESSON Curves over Finite Fields Moving from real numbers to finite fields for practical cryptography 1. The Problem with Real Numbers Elliptic curves over the reals (y² = x³ + ax + b) look elegant, but have critical flaws for cryptography: Infinite precision: Real numbers require arbitrary precision arithmetic Continuous curves: Points form a smooth, continuous set Computational inefficiency: Floating-point operations are slow and imprecise No discrete logarithm: The core cryptographic hardness assumption doesn't work A finite field F p contains exactly p elements where p is prime: All operations (addition, subtraction, multiplication, division) are performed mod p, giving results that wrap around within the field. The same elliptic curve equation works, but now with modular arithmetic: Points (x, y) satisfy this congruence where x, y ∈ F p . We also require the non-singularity condition: Unlike the continuous real curve, elliptic curves over finite fields produce a finite set of discrete points : For each x ∈ F p , compute x³ + ax + b (mod p) Check if the result is a quadratic residue (has a square root mod p) If yes, the square roots give two y-values (or one if y = 0) 5. Group Order and Hasse's Bound The number of points #E(F p ) on the curve is called the group order . Hasse's theorem bounds this quantity: This means the number of points is approximately p, within a range of roughly 2√p. 6. Point Addition Formulas (mod p)

This is the written version of the interactive lesson above. See the full Cryptography course.