## 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 = p ^{r}* elements, where

*p*is prime and

*r > 1*.

**Addition** in *GF(p ^{r})* can be implemented differently than the usual addition modulo

*p*: Elements are interpreted as polynomials of degree

^{r}*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(p ^{r})*) and with coefficients again modulo

*p*.

In the case of *p = 2*, i.e. our favorite *GF(2 ^{r})*, elements in the field require exactly

*r*bits for representation; addition and subtraction also become a simple XOR.

**Multiplication and division in GF(2^{r})**

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

*|2*,

^{0}|_{5}*|2*,

^{1}|_{5}*|2*,

^{2}|_{5}*|2*,

^{3}|_{5}*|2*i.e.,

^{4}|_{5}*1, 2, 4, 3, …*. and

*α*=

^{q-1}*α*= 1.

^{0}(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}
## Leave a Reply

You must be logged in to post a comment.