Modular Arithmetic Refresher

ECDSA lives inside finite fields and elliptic curves over them. Foundations first.

A finite field F_p (p prime) is just integers {0, 1, ..., p-1} with addition and multiplication taken mod p. Examples:

• F_5 = {0,1,2,3,4}. 3+4=7 mod 5 = 2. 3*4=12 mod 5 = 2.
• F_7: 4*5 = 20 mod 7 = 6.

Why prime? Every nonzero element has a multiplicative inverse — division works. In F_4 (non-prime modulus 4), 2 has no inverse.

Modular inverse: a^(-1) mod p is the x such that a*x ≡ 1 (mod p).

Compute via extended Euclidean algorithm (or Fermat's little theorem since p is prime: a^(p-2) mod p).

Why care? Elliptic curve point arithmetic divides by (x2-x1) — translates to "multiply by modular inverse". One modular inverse per addition.

pow(base, exp, mod) is built-in in Python — fast modular exponentiation.