Learn you Galois Fields for Great Good (05)
Navigation  first  previous  next
Polynomial Fields GF(p^k)
This is part 5 of a series on Abstract Algebra. In the last part, we discussed arithmetic over polynomials. This time we'll show how we can use polynomials to construct more finite fields. This is the hardest required section of the series. We will use a lot of abstraction. You may need to read it a few times and do extra exercises. But, after mastering this section, you will be wellprepared to understand and implement real applications such as AES Encryption!
Coefficients from an arbitrary Field
As we discussed previously, addition and multiplication of polynomials are operations upon the coefficients.
In particular:
Operation on Polynomials: A, B  Operation on the Coefficients: a_i, b_i 

addition (A+B)  add pointwise: a_i + b_i 
multiplication (A*B)  convolve [a_n, ..., a_0] with [b_n, ..., b_0] 
Notice that the operations on coefficients require a Field of some kind. In the previous section we implicitly used the Real Numbers. But we don't have to use Real Numbers. We can instead use any Field!
Let's do some examples using GF(5)
for the polynomial coefficients.
This means that each coefficient must be in the set {0, 1, 2, 3, 4}
Addition:
(2x^2 + 3) + (4x^2 + 2x + 2)
(2+4)x^2 + (0+2)x + (3+2)
(1)x^2 + (2)x + (0) [addition in GF(5)]
x^2 + 2x
Multiplication:
(2x + 3) * (3x + 1)
(2x * 3x) + (2x * 1) + (3 * 3x) + (3 * 1)
(2*3)x^2 + (2*1)x + (3*3)x + (3*1)
x^2 + 2x + 4x + 3 [multiplication in GF(5)]
x^2 + (2+4)x + 3
x^2 + x + 3 [addition in GF(5)]
Take a moment to think about this. It's abstract and unfamiliar, but it is absolutely key.
Exercise: Using GF(7)
for coefficients, compute (2x^2 + 3) + (4x^2 + 2x + 2)
Exercise: If we use GF(2)
for coefficients, how would we compute (2x^2 + 3) + (4x^2 + 2x + 2)
? Notice that 2, 3, 4 are not elements of GF(2). But 2 == 0 (mod 2), 3 == 1 (mod 2), 4 == 0 (mod 2)
. Convince yourself the answer would be 1.
Exercise: Using GF(2)
for coefficients, compute (x^2 + 1) + (x^2 + x + 1)
Exercise: Using GF(5)
for coefficients, compute (2x^2 + 1) * (2x^2 + 3)
Exercise: Using GF(2)
for coefficients, compute (x + 1) * (x)
More notation
The previous exercises (you did do them, right? ðŸ˜‘) demonstrate that the Field we select for the coefficients of a polynomial is quite important. Mixing this up can cause some serious confusion. So, mathematicians introduced a special notation to describe it precisely.
We will denote:
F[x]
for the set of all polynomials using F
as the Field for coefficients.
Some examples:
R[x] [polynomials using the realnumbers for coefficients]
Q[x] [polynomials using the rationalnumbers for coefficients]
GF(3)[x] [polynomials using GF(3)]
GF(5)[x] [polynomials using GF(5)]
Size of F[X]
Let's be explicit and list out all the polynomials of order < 3 that we have in GF(3)[x]
:
0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2,
x^2, x^2 + 1, x^2 + 2, x^2 + x, x^2 + x + 1, x^2 + x + 2, x^2 + 2x, x^2 + 2x + 1, x^2 + 2x + 2,
2x^2, 2x^2 + 1, 2x^2 + 2, 2x^2 + x, 2x^2 + x + 1, 2x^2 + x + 2, 2x^2 + 2x, 2x^2 + 2x + 1, 2x^2 + 2x + 2,
There are 27 such polynomials in GF(3)[x]
. Notice that 27 = 3^3
. This is no accident.
In general when polynomial order < m
size(F[x]) = size(F) ^ m
Some examples:
Coefficient Field (F ) 
Polynomial Order Bound (m ) 
Size of F[x] for order < m 

GF(5) 
2 
5^2 = 25 
GF(5) 
3 
5^3 = 125 
GF(2) 
2 
2^2 = 4 
GF(2) 
8 
2^8 = 256 
GF(p) 
k 
p^k 
This table suggests a few things:
 For computing,
GF(2)[x]
with order < 8 has256
elements, the same as an 8bit byte!  In general
GF(p)[x]
with order < k can possibly represent a field withp^k
elements, orGF(p^k)
Exercise: List the polynomials in GF(2)[x]
with order < 3. How many does the theory predict?
More representations
Let's consider vector notation and again list out the polynomials of order < 3 that we have in GF(3)[x]
:
[0, 0, 0], [0, 0, 1], [0, 0, 2],
[0, 1, 0], [0, 1, 1], [0, 1, 2],
[0, 2, 0], [0, 2, 1], [0, 2, 2],
[1, 0, 0], [1, 0, 1], [1, 0, 2],
[1, 1, 0], [1, 1, 1], [1, 1, 2],
[1, 2, 0], [1, 2, 1], [1, 2, 2],
[2, 0, 0], [2, 0, 1], [2, 0, 2],
[2, 1, 0], [2, 1, 1], [2, 1, 2],
[2, 2, 0], [2, 2, 1], [2, 2, 2]
Observe that the sequence behaves like number in base3. From the "ones"
column, we carry into the "threes"
column and then carry into the "nines"
column.
This observation gives us another way to represent our polynomials. We can represent any polynomial from GF(p)[x]
as "ordinary numbers" in Base p
.
For example, the following are all equivalent representations of the same element of GF(3)[x]
:
2x^2 + x + 1
[2, 1, 1]
22 [Because 22 = 2*3^2 + 1*3^1 + 1*3^0]
This representation allows us to talk about polynomials as ordinary numbers. We will do this extensively in the
following sections. This is quite common in the literature and can be quite confusing. The key is that we are NOT
actually talking about numbers like you're used to. It's instead just a shorthand. Its easier to write 22
than to
write 2x^2 + x + 1
. If you ever get confused, just convert back to polynomials.
Let's list the first few polynomials of GF(3)[x]
with all representations sidebyside:
Polynomial  Vector  Number 

0 
[0, 0, 0] 
0 
1 
[0, 0, 1] 
1 
2 
[0, 0, 2] 
2 
x 
[0, 1, 0] 
3 
x + 1 
[0, 1, 1] 
4 
x + 2 
[0, 1, 2] 
5 
2x 
[0, 2, 0] 
6 
2x + 1 
[0, 2, 1] 
7 
2x + 2 
[0, 2, 2] 
8 
x^2 
[1, 0, 0] 
9 
x^2 + 1 
[1, 0, 1] 
10 
... etc ...  ... etc ...  ... etc ... 
Exercise: Complete the above table for order < 3
Exercise: Build a similar comparison table for GF(2)[x]
where order < 4. What's the largest number (in all representations)? Why?
Exercise: From 56
, determine the coefficients for the corresponding polynomial in GF(2)[x]
. This is a very important skill to have for later sections. What common operation in
computing are you doing in this exercise?
Exercise: Convert x^6 + x + 1
from GF(2)[x]
into the decimal number representation.
The big problems on the road to GF(p^k)
We're finally ready to construct fields from our polynomials in GF(p)[x]
.
But there are two big problems:

When we multiply two polynomials, the order grows. We cannot have a finite field if the order grows infinitely. As an example, consider:
x*(x+1) = x^2 + x
andx*(x^2 + x) = x^3 + x^2

We stated in the previous section that we don't have multiplicative inverses. This is an absolute requirement for a Field.
There happens to be a single solution for both of these problems. Just like with modular arithmetic, we'll simply use a "modulus polynomial"
. And, we'll need that to be a "prime modulus polynomial".
Irreducible Polynomials
An irreducible polynomial Q
is a polynomial in F[x]
such that no other polynomial divides it evenly (excluding 1
and Q
).
Example, for GF(3)[x]
, we can show that x^2 + 1
is an irreducible polynomial:
(x^2 + 1) / (x) = x rem 1
(x^2 + 1) / (x + 1) = x + 2 rem 2
(x^2 + 1) / (x + 2) = x + 1 rem 2
(x^2 + 1) / (2x) = 2x rem 1
(x^2 + 1) / (2x + 1) = 2x + 2 rem 2
(x^2 + 1) / (2x + 2) = 2x + 1 rem 2
We can also call these polynomials "prime", just like integers that are prime.
Exercise: Is x^2 + 1
an irreducible polynomial in GF(2)[x]
? Why or why not?
Exercise: Is x^2 + x + 1
an irreducible polynomial in GF(2)[x]
? Why or why not?
Exercise: Is x^2 + x
be an irreducible polynomial for some F[x]
? Why or why not?
Intermission
Whew, That's a lot of info!
Let's take a short break. You earned it!
Your mood  Video Link 

Whoa, that's heavy  enjoy 
Cute Cats  enjoy 
Epic Fails  enjoy 
Comedy Legal Docs  enjoy 
Nerdy Raps  enjoy 
Nerds talking about Emacs  enjoy 
Surprise Me  enjoy (you asked for it) 
Feeling refreshed? Good!
Let's build a new Field!
GF(3^2) by example
Using the irreducible polynomial Q = x^2 + 1
, we will build GF(3^2)
or GF(9)
. Just like modular arithmetic, we define our operations as
normal addition and multiplication, but with a final "modulus" step.
Consider the polynomials from GF(3)[x]
with order < 2:
A = 2x + 1
B = x
And we multiply them to get C:
C = 2x^2 + x
But, C
is too big and isn't in GF(3)[x]
with order < 2. So, we can apply our irreducible polynomial by doing a longdivision and keeping only the remainder.
C % Q = (2x^2 + x) % (x^2 + 1)
= x + 1
Exercise: Check this calculation yourself.
Similarly, we can now find inverses:
inv(2x + 1) = 2x + 2
Checking:
(2x + 1) * (2x + 2)
poly_multiply((2x + 1), (2x + 2)) % Q
[(2*2)x^2 + (2*2 + 1*2)x + (1*2)] % Q
(x^2 + 2) % Q
(x^2 + 2) % (x^2 + 1)
1
Thus, we can manipulate expressions now the way that the algebra gods intended
(2x + 1) * (x) = (x + 1)
inv(2x + 1) * (2x + 1) * (x) = inv(2x + 1) * (x + 1)
(1) * (x) = (2x + 2) * (x + 1)
x = (2x^2 + x + 2) % (x^2 + 1)
x = x
With this, we've constructed GF(3^2)
or GF(9)
. Notationally, we might say that we've constructed GF(9)
as:
GF(9) = G(3)[x]/(x^2 + 1)
We won't use this notation much, but it's useful in some cases since different irreducible polynomials will lead to different relationships in the resulting field.
Exercise: Compute x * x
in our GF(9)
field using the irreducible polynomial x^2 + 1
.
Exercise: Determine the inverse of x
in our GF(9)
field using the irreducible polynomial x^2 + 1
.
Exercise: Build a multiplication table for GF(2^3)
using the irreducible polynomial x^3 + x + 1
.
Operation tables for GF(3^2)
We'll specify the operation tables using the ordinary decimal number representation. If you're confused, convert them back to polynomials and workthrough the calculations.
For Addition:
+  0  1  2  3  4  5  6  7  8 

0  0  1  2  3  4  5  6  7  8 
1  1  2  0  4  5  3  7  8  6 
2  2  0  1  5  3  4  8  6  7 
3  3  4  5  6  7  8  0  1  2 
4  4  5  3  7  8  6  1  2  0 
5  5  3  4  8  6  7  2  0  1 
6  6  7  8  0  1  2  3  4  5 
7  7  8  6  1  2  0  4  5  3 
8  8  6  7  2  0  1  5  3  4 
Similarly for Multiplication using Q = x^2 + 1
(also notated as 10
)
*  0  1  2  3  4  5  6  7  8 

0  0  0  0  0  0  0  0  0  0 
1  0  1  2  3  4  5  6  7  8 
2  0  2  1  6  8  7  3  5  4 
3  0  3  6  2  5  8  1  4  7 
4  0  4  8  5  6  1  7  2  3 
5  0  5  7  8  1  3  4  6  2 
6  0  6  3  1  7  4  2  8  5 
7  0  7  5  4  2  6  8  3  1 
8  0  8  4  7  3  2  5  1  6 
Let's check some addition:
5 + 6
(x + 2) + (2x) [convert to polynomial representation]
(1+2)x + (2+0) [polynomial addition: group coefficients]
0x + 2 [coefficient addition in GF(3)]
2 [final answer: polynomial and decimal representations are the same]
And multiplication:
5 * 6
{x + 2} * {2x} [convert to polynomial representation]
[(x + 2) * (2x)] % Q [apply the definition of multiplication]
[(x * 2x) + (2 * 2x)] % Q [polynomial multiplication]
[(2)x^2 + (2*2)x] % Q [rearrange]
[(2)x^2 + (1)x] % Q [coefficient multiplication in GF(3)]
(2x^2 + x) % Q [simplify]
(2x^2 + x) % (x^2 + 1) [expand modulus: irreducible polynomial]
(2x^2 + x)  2(x^2 + 1) [need to subtract it off two times)
x + (2) [result]
x + 1 [apply the negation]
4 [convert to decimal representation]
Exercise: Check as many additions and multiplications as you need to until you fully understand where this table comes from. If the above table still feels like magic, you haven't done enough exercises.
GF(p^k) in General
Let's formalize everything into a generalpurpose theory for building any GF(p^k)
from GF(p)
.
First, we must determine the k
that we wish to use. Then, we select an irreducible
polynomial Q
of order k
from GF(p)[x]
. Finally, we define our addition and multiplication
as follows:
Operation  Calculation 

add (+) 
poly_add(A, B) 
mult (*) 
poly_mod(poly_mult(A, B), Q) 
Where:
poly_add
is ordinary polynomial additionpoly_mult
is ordinary polynomial multiplicationpoly_mod
is ordinary polynomial longdivision, but we keep the remainder only
Notice that we don't apply the modulus operation on the addition. We could do it, but it is superfluous.
Since the irreducible polynomial is of larger order than any element in GF(p^k)
, all additions of
the coefficients will be "smaller" than it.
GF(p^k) Examples
Lastly, we give some examples of various parameters that result in a Field. The values: p
, k
, and Q
need to be selected upfront before using a Field. Commonly Q
is taken from some table after selecting
values p
and k
.
Here are some Fields:
p 
k 
Q 
F[x]/Q 
GF(n=p^k) 

3 
2 
x^2 + 1 
GF(3)[x]/(x^2+1) 
GF(9) 
2 
2 
x^2 + x + 1 
GF(2)[x]/(x^2+x+1) 
GF(4) 
2 
8 
x^8 + x^4 + x^3 + x^2 + 1 
GF(2)[x]/(x^8+x^4+x^3+x^2+1) 
GF(256) 
2 
8 
x^8 + x^5 + x^3 + x + 1 
GF(2)[x]/(x^8+x^5+x^3+x+1) 
GF(256) 
Notice here that we've constructed GF(256)
with two different irreducible polynomials. These are NOT
equivalent constructions. They happen to share the same numbers, but are otherwise distinct.
Conclusion
This is a lot of abstraction in one place so we'll finish with a quick summary of what we've done.
 We demonstrated that we can build polynomials with coefficients from any field
F
 We introduced the notation
F[x]
to represent all such polynomials over a fieldF
 We explored the size of
GF(p)[x]
for order <k
 We introduced the "number" representation for polynomial elements of
GF(p)[x]
and compared all 3 representations.  We presented Irreducible Polynomials as the polynomial version of a Prime Number
 We demonstrated multiplications in
GF(3^2)
using the irreducible polynomialx^2 + 1
 We gave a general framework for constructing a field
GF(p^k)
As we mentioned in the beginning, this is the most challenging section. Feel free to spend some time with it to fully digest it. Do a lot of examples. Read wikipedia. Consider consulting supplemental resources and returning for a reread. Again, active learning is required. If you struggle a bit, just remember that math is hard for everyone.
The good news is that most of the pure theory is over. In the next sections we'll move on to computer science applications.
Next time, we'll be coding!