Elliptic Curve Point Addition
Group law on E: y² = x³ + ax + b over ℝ and over finite fields 𝔽_p
Over ℝ
Over 𝔽_p
Scalar mult
Curve y² = x³ + ax + b
a =
-1
b =
0
Point P (click on curve):
P = (click curve)
Point Q (right-click):
Q = (right-click)
Compute P + Q
Compute 2P
R = P + Q = ?
Addition law:
λ = (y₂-y₁)/(x₂-x₁)
x₃ = λ²-x₁-x₂
y₃ = λ(x₁-x₃)-y₁
Doubling:
λ = (3x₁²+a)/(2y₁)
Identity:
point at infinity 𝒪
P + (-P) = 𝒪; -P = (x,-y)
E over 𝔽_p
Prime p:
17
a:
2
b:
2
Base point G:
Show kG for k=1..ord
All formulas work mod p!
Division → modular inverse.
Hasse's theorem:
|#E(𝔽_p) - (p+1)| ≤ 2√p
ECDLP:
given P, Q=kP,
find k — believed hard.
Basis of ECC cryptography.
secp256k1: y²=x³+7, p≈2²⁵⁶
(Bitcoin's curve)
Scalar Multiplication kG
p (prime):
23
k =
7
Double-and-Add
Double-and-add:
Binary representation of k
→ O(log k) group operations
k=7=111₂:
Start: R=G
bit 1: R=2R+G (double+add)
bit 1: R=2R+G
= 7G ✓
Security:
ECDLP in group of
order n needs ~√n steps
(baby-step giant-step)