# 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
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}`

``````(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)]

``````

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:

• For computing, `GF(2)[x]` with order < 8 has `256` elements, the same as an 8-bit byte!
• In general `GF(p)[x]` with order < k can possibly represent a field with `p^k` elements, or `GF(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 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!

Whoa, that's heavy enjoy
Cute Cats enjoy
Epic Fails enjoy
Comedy Legal Docs enjoy
Nerdy Raps 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.

+ 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

``````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:

• `poly_add` is ordinary polynomial addition
• `poly_mult` is ordinary polynomial multiplication
• `poly_mod` is ordinary polynomial long-division, 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 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!