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 well-prepared 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 real-numbers for coefficients]
Q[x]            [polynomials using the rational-numbers 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:

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 base-3. 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 side-by-side:

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:

  1. 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 and x*(x^2 + x) = x^3 + x^2

  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 long-division 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 work-through 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 general-purpose 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:

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 up-front 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.

  1. We demonstrated that we can build polynomials with coefficients from any field F
  2. We introduced the notation F[x] to represent all such polynomials over a field F
  3. We explored the size of GF(p)[x] for order < k
  4. We introduced the "number" representation for polynomial elements of GF(p)[x] and compared all 3 representations.
  5. We presented Irreducible Polynomials as the polynomial version of a Prime Number
  6. We demonstrated multiplications in GF(3^2) using the irreducible polynomial x^2 + 1
  7. 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 re-read. 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!

Let's Go!