Constructing Finite Fields


Ok.

As a shortcut to get to GF(81), you can find an irreducible quartic over GF(3). Adjoin a root alpha and all elements are of the form a + b*alpha + c*alpha^2 + d*alpha^3 for a,b,c,d in GF(3).

So. To build GF(27), we find an irreducible cubic over Z(3), call its root β, and the basis vectors become β0, β1, β2.

Ok. Let’s pick x3+2x+2. For 0, 1, 2, this expression evaluates to 2, 2, 2 – no root in Z(3). Cool. We call the root β. Rearranging,β3 = β+1.

(hmm … I wonder how you factor this? The quadratic was easy: x2-2=0 factors into (x-α)(x+α) )

Well! This makes much more sense! No more “What is αβ?”. Anything bigger than ß2 reduces down, and it does so in a way that is interesting enough to be believable:

β3 = β+1
β4 = (β+1)β = β2
β5 = (β+1)β2 = β322+β+1
β6 = (β+1)(β+1) = β2+2β+1

What, I wonder, does our multiplication table look like?

001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222
002 001 020 022 021 010 012 011 200 202 201 220 222 221 210 212 211 100 102 101 120 122 121 110 112 111
010 020 100 110 120 200 210 220 011 021 001 111 121 101 211 221 201 022 002 012 122 102 112 222 202 212
011 022 110 121 102 220 201 212 111 122 100 221 202 210 001 012 020 222 200 211 002 010 021 112 120 101
012 021 120 102 111 210 222 201 211 220 202 001 010 022 121 100 112 122 101 110 212 221 200 002 011 020
020 010 200 220 210 100 120 110 022 012 002 222 212 202 122 112 102 011 001 021 211 201 221 111 101 121
021 012 210 201 222 120 111 102 122 110 101 002 020 011 212 200 221 211 202 220 121 112 100 001 022 010
022 011 220 212 201 110 102 121 222 211 200 112 101 120 002 021 010 111 100 122 001 020 012 221 210 202
100 200 011 111 211 022 122 222 110 210 010 121 221 021 102 202 002 220 020 120 201 001 101 212 012 112
101 202 021 122 220 012 110 211 210 011 112 201 002 100 222 020 121 120 221 022 111 212 010 102 200 001
102 201 001 100 202 002 101 200 010 112 211 011 110 212 012 111 210 020 122 221 021 120 222 022 121 220
110 220 111 221 001 222 002 112 121 201 011 202 012 122 010 120 200 212 022 102 020 100 210 101 211 021
111 222 121 202 010 212 020 101 221 002 110 012 120 201 100 211 022 112 220 001 200 011 122 021 102 210
112 221 101 210 022 202 011 120 021 100 212 122 201 010 220 002 111 012 121 200 110 222 001 211 020 102
120 210 211 001 121 122 212 002 102 222 012 010 100 220 221 011 101 201 021 111 112 202 022 020 110 200
121 212 221 012 100 112 200 021 202 020 111 120 211 002 011 102 220 101 222 010 022 110 201 210 001 122
122 211 201 020 112 102 221 010 002 121 210 200 022 111 101 220 012 001 120 212 202 021 110 100 222 011
200 100 022 222 122 011 211 111 220 120 020 212 112 012 201 101 001 110 010 210 102 002 202 121 021 221
201 102 002 200 101 001 202 100 020 221 122 022 220 121 021 222 120 010 211 112 012 210 111 011 212 110
202 101 012 211 110 021 220 122 120 022 221 102 001 200 111 010 212 210 112 011 222 121 020 201 100 002
210 120 122 002 212 211 121 001 201 111 021 020 200 110 112 022 202 102 012 222 221 101 011 010 220 100
211 122 102 010 221 201 112 020 001 212 120 100 011 222 202 110 021 002 210 121 101 012 220 200 111 022
212 121 112 021 200 221 100 012 101 010 222 210 122 001 022 201 110 202 111 020 011 220 102 120 002 211
220 110 222 112 002 111 001 221 212 102 022 101 021 211 020 210 100 121 011 201 010 200 120 202 122 012
221 112 202 120 011 101 022 210 012 200 121 211 102 020 110 001 222 021 212 100 220 111 0
02
122 010 201
222 111 212 101 020 121 010 202 112 001 220 021 210 102 200 122 011 221 110 002 100 022 211 012 201 120

Let’s check it for at least one. According to our table, 211*101=212.

(2β2+β+1)(β2+1)
= (2β432)+(2β2+β+1)
= 2β43+3β2+β+1
≡ 2β43+β+1
= 2(β2+β)+(β+1)+β+1
= 2β2+2β+β+1+β+1
= 5β2+4β+2
≡ 2β2+1β+2

QED!


Ok. Why does it have to be an irreducible polynomial? What happens if you pick a polynomial that isn’t irreducible? I expect that what you wind up with isn’t a group.

(x+1)(x+1)(x)
(x2+2x+1)(x)
x3+2x2+x
γ3 = γ2+2γ
γ4 = γ3+2γ2

001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222
002 001 020 022 021 010 012 011 200 202 201 220 222 221 210 212 211 100 102 101 120 122 121 110 112 111
010 020 100 110 120 200 210 220 021 001 011 121 101 111 221 201 211 012 022 002 112 122 102 212 222 202
011 022 110 121 102 220 201 212 121 102 110 201 212 220 011 022 000 212 220 201 022 000 011 102 110 121
012 021 120 102 111 210 222 201 221 200 212 011 020 002 101 110 122 112 121 100 202 211 220 022 001 010
020 010 200 220 210 100 120 110 012 002 022 212 202 222 112 102 122 021 011 001 221 211 201 121 111 101
021 012 210 201 222 120 111 102 112 100 121 022 010 001 202 220 211 221 212 200 101 122 110 011 002 020
022 011 220 212 201 110 102 121 212 201 220 102 121 110 022 011 000 121 110 102 011 000 022 201 220 212
100 200 021 121 221 012 112 212 120 220 020 111 211 011 102 202 002 210 010 110 201 001 101 222 022 122
101 202 001 102 200 002 100 201 220 021 122 221 022 120 222 020 121 110 211 012 111 212 010 112 210 011
102 201 011 110 212 022 121 220 020 122 221 001 100 202 012 111 210 010 112 211 021 120 222 002 101 200
110 220 121 201 011 212 022 102 111 221 001 202 012 122 020 100 210 222 002 112 010 120 200 101 211 021
111 222 101 212 020 202 010 121 211 022 100 012 120 201 110 221 002 122 200 011 220 001 112 021 102 210
112 221 111 220 002 222 001 110 011 120 202 122 201 010 200 012 121 022 101 210 100 212 021 211 020 102
120 210 221 011 101 112 202 022 102 222 012 020 110 200 211 001 121 201 021 111 122 212 002 010 100 220
121 212 201 022 110 102 220 011 202 020 111 100 221 012 001 122 210 101 222 010 002 120 211 200 021 112
122 211 211 000 122 122 211 000 002 121 210 210 002 121 121 210 002 001 120 212 212 001 120 120 212 001
200 100 012 212 112 021 221 121 210 110 010 222 122 022 201 101 001 120 020 220 102 002 202 111 011 211
201 102 022 220 121 011 212 110 010 211 112 002 200 101 021 222 120 020 221 122 012 210 111 001 202 100
202 101 002 201 100 001 200 102 110 012 211 112 011 210 111 010 212 220 122 021 222 121 020 221 120 022
210 120 112 022 202 221 101 011 201 111 021 010 220 100 122 002 212 102 012 222 211 121 001 020 200 110
211 122 122 000 211 211 122 000 001 212 120 120 001 212 212 120 001 002 210 121 121 002 210 210 121 002
212 121 102 011 220 201 110 022 101 010 222 200 112 021 002 211 120 202 111 020 001 210 122 100 012 221
220 110 212 102 022 121 011 201 222 112 002 101 021 211 010 200 120 111 001 221 020 210 100 202 122 012
221 112 222 110 001 111 002 220 022 210 101 211 102 020 100 021 212 011 202 120 200 121 012 122 01
0
201
222 111 202 121 010 101 020 212 122 011 200 021 210 102 220 112 001 211 100 022 110 002 221 012 201 120

And as you can see, some of the columns don’t have a multiplicative inverse, some cells multiply out to zero.


Still not 100% sure what this all – you know – means. I envisage these vectors as being like n speedometer wheels, each wheel having p numbers on it. Addition means advancing all the wheels by some amount each. The way that addition works means that each wheel is independent of all the others. The linear aspect of it means that 3x is the same as doing x 3 times.

The associativity rule means that to multiply something by (a+b), you can roll the wheels forward according to a, and then roll them forward according to b – these no interaction between the motions occasioned by a and b.

But we agreed earlier that multiplication must affect multiple wheels. How so? Well – multiplying two values just adds together the effect of multiplying together each pair of wheels in the two values … but each pair of wheels in the multiplication results in some combination of other wheels being rolled forward in the final sum. Moreover, the combinations have to lock together – you can’t just pick arbitrarily.

There’s a lot I still don’t “get”. Maybe … maybe I have enough to return to page 7. Or was it 6?

Advertisements

2 Responses to Constructing Finite Fields

  1. BrettW says:

    Looks good. As for the whole irreducibility thing, if you extend via a reducible polynomial, you will end up with the same field you started with. Your alpha will just be some element you already had. If you have a consistent simplification technique to build your group table, you’ll find you have repeated rows and columns which, as you say, makes it not a group any more.

  2. Paul Murray says:

    We can view the problem of constructing a finite field as being the problem of finding a set of basis vectors, viewed entirely in terms of “rolling the speedo wheels forward”, that allow us to “reach” every possible combination of the N speedo wheels from [1,0,0] except for [0,0,0].

    Reminds me a bit of the 3-sat problem. 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: