Understand Finite Fields and Modular Arithmetic
The Math That Keeps Appearing in Every Crypto Primitive
Finite fields are algebraic structures where addition, subtraction, multiplication, and division all work cleanly and produce results that stay within a fixed finite set. They appear in AES, elliptic curve cryptography, and error-correcting codes — not by coincidence but because their properties are exactly what those algorithms require.
The Integers Mod p
When p is prime, the set Z_p = {0, 1, ..., p-1} with addition and multiplication performed modulo p forms a field. Every nonzero element has a multiplicative inverse: for any a not divisible by p, there exists b such that a * b = 1 mod p. This is not true
Fermat's Little Theorem
For prime p and any a not divisible by p, a^(p-1) = 1 mod p. This gives a direct formula for the inverse: a^(p-2) mod p. It also underlies RSA key generation and the correctness of RSA decryption — the exponent arithmetic works because of this theorem.
The Multiplicative Group and Discrete Logarithm
The nonzero elements of Z_p form a cyclic group Z_p* of order p-1 under multiplication. This group has generators — elements g such that the powers g^1, g^2, ..., g^(p-1) cycle through all nonzero elements. The discrete logarithm problem is: given g and g
Field Extensions: GF(2^8)
Finite fields need not have prime size. GF(2^n) is constructed as polynomials with coefficients in GF(2) = {0, 1}, modulo an irreducible polynomial of degree n. GF(2^8) has 256 elements. Addition is XOR of coefficients. Multiplication uses the irreducible
256
128
AES and GF(2^8)
AES uses GF(2^8) with the irreducible polynomial x^8 + x^4 + x^3 + x + 1. The SubBytes step applies a nonlinear S-box defined using field inversion in GF(2^8). The MixColumns step multiplies a state vector by a fixed matrix over GF(2^8). These operations
Go Deeper: Finite Fields as Instances of Abstract Algebra
Finite fields are instances of abstract algebraic structures — groups, rings, and fields — that recur throughout cryptography. Understanding the abstract structure behind them makes the patterns visible and reveals why certain constructions work at a deeper level than implementation details.
