Elliptic Curve Arithmetic — Field Reference

Modular Arithmetic — Reduction Rules

Master Rule

(a op b) mod p = ((a mod p) op (b mod p)) mod p
// valid for op = + − × — reduce inputs before and output after

Operation	Rule	Key note
Addition	(a + b) mod p = ((a mod p) + (b mod p)) mod p	Result < 2p; at most one subtraction of p needed
Subtraction	(a − b) mod p = ((a mod p) − (b mod p) + p) mod p	+p prevents negatives; always add p before reducing
Multiplication	(a × b) mod p = ((a mod p) × (b mod p)) mod p	Reduce both first; product is at most (p−1)²
Exponentiation	a^e mod p = (a mod p)^e mod p	Reduce base first; reduce after every squaring
Division ⚠	(a / b) mod p = (a mod p) × (b⁻¹ mod p) mod p	No direct division — use modular inverse of b

Modular Inverse — two methods

// Method 1: Fermat's little theorem (p must be prime)
b⁻¹ ≡ b^(p−2) (mod p)

// Method 2: Extended Euclidean — find k, j such that b·k + p·j = 1
// then k mod p is the inverse

Interactive — Modular Inverse Calculator

a (find a⁻¹)

p (prime modulus)

Interactive — Modular Arithmetic Calculator

p (modulus)

operation

Point Addition — P + Q

Curve

y² = x³ + ax + b (mod p)

Slope λ

λ = (y_Q − y_P) · (x_Q − x_P)⁻¹ mod p

Result Point R = P + Q

x_R = λ² − x_P − x_Q mod p
y_R = λ(x_P − x_R) − y_P mod p

Compute Δy = y_Q − y_P mod p and Δx = x_Q − x_P mod p

Find (Δx)⁻¹ mod p using Fermat: (Δx)^(p−2) mod p

λ = Δy · (Δx)⁻¹ mod p

x_R = λ² − x_P − x_Q mod p

y_R = λ(x_P − x_R) − y_P mod p

Special cases: If P = Q → use point doubling. If x_P = x_Q but y_P ≠ y_Q → P + Q = 𝒪 (point at infinity, the identity). P + 𝒪 = P always.

Point Doubling — 2P

Tangent slope λ

λ = (3x_P² + a) · (2y_P)⁻¹ mod p

Result Point R = 2P

x_R = λ² − 2x_P mod p
y_R = λ(x_P − x_R) − y_P mod p

Numerator: 3x_P² + a mod p

Denominator: 2y_P mod p. Find its modular inverse.

λ = numerator · (denominator)⁻¹ mod p

x_R = λ² − 2x_P mod p

y_R = λ(x_P − x_R) − y_P mod p

Special case: If y_P = 0 → 2P = 𝒪 (tangent is vertical).

Interactive — λ & Point Calculator

Curve parameters

p (prime)

operation

Point P

x_P

y_P

Point Q

x_Q

y_Q

Scalar Multiplication — nP (Double-and-Add)

Algorithm — Double-and-Add

// Write n in binary: n = b_kb_k−1...b₁b₀
1. R = P // start: leading 1-bit
2. For each remaining bit (left to right):
R = 2R // always double
if bit = 1: R = R + P // add only on 1-bits
3. Return R

Operation count

Doublings: ⌊log₂(n)⌋
Additions: popcount(n) − 1
Total: much less than n − 1

Analogy to fast exp

Double → Square (R²)
Add P → Multiply by b
Same binary scan, same logic

Interactive — Scalar Multiplication Calculator

p (prime)

n (scalar, 1–64)

x_P

y_P

Fast Exponentiation — Square-and-Multiply

Algorithm

R = b // start
bit=0 → R = R² mod p
bit=1 → R = R² · b mod p

Complexity

Naive: e − 1 multiplications
Fast: ~2 log₂(e) operations
For e=2048: 4000 vs 10⁶¹⁶

Interactive — Fast Exponentiation Calculator

base (b)

exponent (e)

modulus (p)

Hasse's Theorem — Point Count Bounds

What does #E mean?

Notation

#E means "the number of points on the elliptic curve E" — it is the order (size) of the group formed by the curve's points.

Specifically, #E counts every pair (x, y) with x, y in {0, 1, …, p−1} that satisfies y² ≡ x³ + ax + b (mod p), plus one extra for the point at infinity 𝒪, which acts as the identity element (the "zero") of the group.

So: #E = (number of (x,y) pairs on the curve) + 1

Why it matters

In elliptic curve cryptography, the security of operations like scalar multiplication nP depends on #E being large (so brute-force is infeasible) and having a large prime factor (to resist Pohlig–Hellman attacks). Hasse's theorem tells you, without counting every point, that #E is always close to p — so picking a large prime p guarantees a large and secure group.

The Theorem

| #E − (p + 1) | ≤ 2√p

// Expanded into lower and upper bounds:
p + 1 − 2√p ≤ #E ≤ p + 1 + 2√p

// Perfect-square form (easier to remember):
(√p − 1)² ≤ #E ≤ (√p + 1)²

Why is the centre p + 1, not p?

Intuition — quadratic residues

For each of the p possible x-values, you compute S = x³ + ax + b mod p and ask: how many y satisfy y² ≡ S?

— If S = 0 → exactly 1 solution (y = 0)
— If S is a quadratic residue (a perfect square mod p) → exactly 2 solutions (y and p−y)
— If S is a non-residue → 0 solutions

Exactly half of {1, …, p−1} are quadratic residues, so averaging over all x: each x contributes exactly 1 point on average. That gives p points from p x-values, plus the point at infinity 𝒪, totalling p + 1 as the expected centre.

Why the error is bounded by 2√p

Hasse (1930s, completed rigorously by Weil 1948) proved that the deviation t = #E − (p+1) can be written as t = α + ᾱ where α is a complex number with |α| = √p. Since |α + ᾱ| ≤ 2|α|, the error is at most 2√p. This is a deep result from algebraic geometry — it's not obvious, but the bound is tight: some curves actually reach #E = p + 1 ± 2√p.

How to calculate bounds by hand

Take your prime p.

Compute √p (decimal approximation is fine — it doesn't need to be exact).

Multiply by 2 to get 2√p.

Lower bound = p + 1 − 2√p, then round up (ceiling) to the nearest integer — #E must be a whole number.

Upper bound = p + 1 + 2√p, then round down (floor).

Example — p = 17

√17 ≈ 4.123 → 2√17 ≈ 8.246
Lower: 18 − 8.246 ≈ 9.754 → ceil = 10
Upper: 18 + 8.246 ≈ 26.246 → floor = 26
Result: 10 ≤ #E ≤ 26

Example — p = 37

√37 ≈ 6.083 → 2√37 ≈ 12.166
Lower: 38 − 12.166 ≈ 25.834 → ceil = 26
Upper: 38 + 12.166 ≈ 50.166 → floor = 50
Result: 26 ≤ #E ≤ 50

Interactive — Hasse Bounds Calculator

p (prime)