Extension Fields March 27, 2006
These are notes from reading “Effective erasure codes for reliable computer communication protocols” by Luigi Rizzo.
An extension field is a field, GF(q) with q = pr elements, where p is prime and r > 1.
Addition in GF(pr) can be implemented differently than the usual addition modulo pr: Elements are interpreted as polynomials of degree r-1 with coefficients in GF(p). The sum of two elements in the field is the sum of their coefficients modulo p
Product is a polynomial product modulo an irreducible polynomial of degree r (one with divisors in GF(pr)) and with coefficients again modulo p.
In the case of p = 2, i.e. our favorite GF(2r), elements in the field require exactly r bits for representation; addition and subtraction also become a simple XOR.
Multiplication and division in GF(2r)
In a prime extension field, all elements can be represented as powers of a single number, α, called the generator. E.g., in GF(5), α = 2, and the elements of the field are |20|5, |21|5, |22|5, |23|5, |24|5 i.e., 1, 2, 4, 3, …. and αq-1 = α0 = 1.
(Is 1 therefore a member of every prime extension field ?)
Each non-zero element of the field, x can thus be written as αkx, and thus:
Multiplication: xy = α|kx+ky|q-1
Quotient: 1/x = α-kx+q-1