Learn you Galois Fields for Great Good (02)
Navigation | first | previous | next
Field Theory
This is part 2 of a series on Abstract Algebra. In this part, we'll extend the idea of a Group into the idea of a Field.
Where we're going
To build a Field, we're basically going to glue two groups together. Something like gluing a car and truck together.
Now, I know what you're thinking: "Hey, they tried that in 60s and it was weird..."
I hear what you're saying, but this is not a Design By Committee blog post, okay... That ends in weird car design also. My blog, my rules.
Our goal is to glue a Car group and and Truck group together and NOT get an El Camino.
Vehicles and Glue
We're going to combine the main two groups we discussed last time into a single unified field. We built an
addition group and a multiplication group last time. For multiplication we need a prime-number, so we'll use
the same n = p prime for each.
Visually:
| Vehicle Type | Operation(s) | Numbers |
|---|---|---|
| Car | + | 0, 1, 2, 3, ..., p-1 |
| Truck | * | 1, 2, 3, ..., p-1 |
| no el camino | +, * | ???? |
Uh oh. Big problem: Zero doesn't behave correctly in a multiplication group!
We said at the beginning that finite fields are like normal math with weird numbers. In normal math, zero is also weird. So weird that it took mathematics a long time to accept it (which is another reason us computer scientists feel compelled to troll mathematicians with it).
Our workaround will be the same as in normal math. Our numbers will be {0, 1, 2, 3, ..., p-1} and we'll define 0 * a = 0 for all numbers a. And for multiplicative inverses and division with zero.. ummm... just don't do that okay?
Congratulations: We've constructed GF(p)!
Before proceeding, I want to explain this notation. GF stands for Galois Field which is just a synonym for Finite Fields named after Évariste Galois who had a short-lived but fascinating life (wiki). In parenthesis the "size" of the field is given. Here we have p numbers so we denote this field as GF(p). Note: infinite-sized fields exist also (e.g. The Real Numbers), but we're only dealing with fields that have a finite amount of numbers.
Exploring GF(5)
Let's make this more concrete by exploring GF(5). First, this notation tells us there are 5 numbers in this field.
Let's denote them as {0, 1, 2, 3, 4}.
Addition in this field is just plain modular-arithmetic addition:
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
Multiplication is similar, with the quirk about 0
| * | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 3 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
Exercise: Convince yourself these tables are correct. Hint: they might not be ;-)
Exercise: What's an easy method to sanity-check a multiplication table? Hint: think about what multiplicative inverses imply about uniqueness.
Additive inverses:
| inv(+) | |
|---|---|
| 0 | 0 |
| 1 | 4 |
| 2 | 2 |
| 3 | 3 |
| 4 | 1 |
Multiplicative inverses:
| inv(*) | |
|---|---|
| 0 | BAD |
| 1 | 1 |
| 2 | 3 |
| 3 | 2 |
| 4 | 4 |
Finally, let's demonstrate an important property of a field.
Consider 4*(2+1) and (4*2) + (4*1). Are these equal?
4*(2+1) = 4*3 = 2
(4*2) + (4*1) = 3 + 4 = 2
Yes! Does this work in general? Also, yes.
The distributive property holds for fields:
a * (b + c) = a*b + a*c
(a + b) * c = a*c + b*c
Exercise: Try more examples. Try some complicated expression. Get a feel for using GF(5). It should "just work".
Exercise: Explore GF(2). Does it still work? What common computer operation is addition? What common computer operation is multiplication?
Exercise: Does GF(4) work if you construct it the same way as above? Why or why not?
Definition
We're now ready to be math lawyers and go all definitional.
A Field is defined as two operations (+ and *) defined over a set of "numbers" which follow these rules:
- Associativity:
(a + b) + c = a + (b + c), (a * b) * c = a * (b * c) - Commutativity:
a + b = b + a, a * b = b * a - Identity: An additive identity (
0) and a multiplicative identity (1) where:a + 0 = a, a * 1 = a - Additive inverses: for each
athere is somebsuch thata + b = 0 - Multiplicative inverses: for each
a != 0there is somebsuch thata * b = 1 - Distributivity:
a * (b + c) = (a * b) + (a * c)
And that's it. You now know what a field is.
This is effectively just formalizing up what is usual and common in the Real Numbers. This is why I say "it just works".
I need to however say one note on "commutativity". Our definition of groups did not require commutativity. This is common in group definitions. But the addition and multiplication groups used in a field DO need commutativity. The modular arithmetic groups are indeed commutative so this is no problem. Since our focus is finite fields and not groups, we won't see any non-commutative groups. If you're curious though, they're not hard to find: permutation groups or Matrix Multiplication Group GL(n,R)
Finally, the definition of Field is very general and says nothing about the size. We can have infinite sized Fields. For example, the Real Numbers are a Field. The Rational Numbers are also a field.
Exercise: Are the infinite set of integers {..., -2, -1, 0, 1, 2, ...} a Field using normal addition and multiplication? Why or why not?
Exercise: (Tricky) Find GF(4). Hint: let a + a = 0 always. Then use the properties of a field to deduce the rest of the addition and multiplication tables. Check that all properties are satisfied.
The Lonely Misfits
We're skipping a very large amount of the standard Abstract Algebra treatment in this series. We're just plucking out the parts that are directly useful to finite-fields. There is a very large and interesting landscape of algebraic structures. These structures strengthen or weaken the various required properties. Most notably I'm skipping Rings. As an example, the integers with normal addtion and multiplication form a Ring. Here's an outline of various algebraic structures if you're curious: link
Next Steps
You should be very comfortable with this material before moving on. If you aren't, go back and do more examples. This is a very cumulative subject and in each section, I will assume you've mastered the previous section.
If you follow everything so far, congrats. You're rockin' math: Time to Celebrate!
Next up, we'll finally begin coding, starting with a GF(p) implementation!