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

Tags
Conversation
Related Tags
Comments
Trackback


Leave a Reply

You must be logged in to post a comment.

This entry was posted on Monday, March 27th, 2006 at 7:16 pm. You can follow any responses to this entry through the RSS 2.0 feed. If you're wondering how to get your own icon next to your comment, go visit gravatar.com and get yourself hooked up.
 steal compass, drive north, disappear...