Elliptic Curves

A short Weierstrass elliptic curve over F_p:

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

with discriminant 4a³ + 27b² ≠ 0 (otherwise it's singular and unsafe).

Examples:

• secp256k1: y² = x³ + 7 (a = 0, b = 7).
• P-256: y² = x³ - 3x + b (specific b).

Points on the curve form an abelian group under "point addition":

• Point P + point Q = R, where R is also on the curve.
• Identity element: ∞ (the "point at infinity").
• For point P = (x, y), inverse −P = (x, -y).

Geometrically (over R):

• Draw a line through P and Q. It hits the curve at a third point R'.
• Reflect over x-axis to get R.

For tangents (P + P), use the curve's slope at P.

Each addition involves:

• One modular inverse (the slope's denominator).
• A few multiplications.

Cost ~O(log p) bit ops per multiplication, dominated by the inverse (or precomputed via projective coords for speed).