Constructing finite fields.


So, anyway. I was at Brett’s blog. An engineer is not a scientist, and likewise a computer programmer is not a mathematician. But we can’t help having a bit of an interest on the discipline that forms the underpinning of what we do.

So. Finite fields. My interest is in writing a program that, if you give it a prime number p and positive n, will generate the field GF(pn) ≡ GF(p)n.

Ok. A field is made up of two interlocking groups (vague memory that there is a thing called a ring?) over some set of atoms. Each group has an identity, an inverse operation etc and the two groups interlock in that one is distributive over the other. The canonical field is the rational numbers under addition and multiplication.

The finite fields GF(p)1 are simply the integers mod p, with addition and multiplication mod p as the field operators. Great! Ok, first problem: what’s the division operator? A little searching turns up the extended gcd algorithm. Brilliant, sorted.

Now then. According to Brett, higher-order finite fields can be built like so:

You find a polynomial that has no root over the field, and you treat its root as an atom in your new group. Let’s call it α. The atoms of the new group become polynomials a+bα. Where a and b are integers p. To continue, you do this again: find a β that’s the root of a polynomial that has no root in the smaller group, and the atoms of the new group become a+bα+cβ.

The addition operator over these values is simply vector addition: you add the a’s, b’s and c’s etc modulo p. The multiplication operator is not so simple – you multiply the polynomial form. Finding the multiplicative inverse … could be fun.

Ok. For a nontrivial example, let’s start with GF(3)1 Here’s the multiplication table (omitting the zero):

1 2
2 1

Awesome! Well – what’s a polynomial that doesn’t have a root in that table? By looking at the diagonal, we see that no value has a square of 2, so the root of x2 – 2 = 0 can be our new α . Re-arranging this, we see that α2 = 2$. The atoms of our new group become (a+bα).

Let’s multiply! (2+2α)(1+2α) = 2 + 6α + 4αα . Since αα = 2, this reduces to 2 + 6α + 8, which becomes 1 when we do everything mod 3.

Our multiplication table now looks like this:

1 2 α α+1 α+2 2α+1 2α+2
2 1 2α+2 2α+1 α α+2 α+1
α 2 α+2 2α+2 1 α+1 2α+1
α+1 2α+2 α+2 1 2α+1 2 α
α+2 2α+1 2α+2 1 α α+1 2
α 1 2α+1 α+1 2 2α+2 α+2
2α+1 α+2 α+1 2 2α+2 α 1
2α+2 α+1 2α+1 α 2 α+2 1

We now want to extend this, to pick a β. By inspecting the diagonal, we see that no element has a square of α+1, so our new β is the root of β2-( α+1 )= 0.

So let’s add this and build a new group!

Ah. A snag. If we simply use the same method to add it, we wind up with 81 elements, because the elements would be a+bβ where a and b are elements of the form a+bα. Obviously, to get just pn of these we have to multiply out. Now, we know what α2 is, and we know what β2 is. But what is αβ?

Well, I know that
α2 = 2
β2 = α+1
And so
(αβ)2 = 2α+2

So to work out what αβ is, I can inspect the diagonal and find if there is some value that might work as αβ. For each value x = a+bα+cβ, calculate out what happens when you square it – substituting in the correct values for α2, β2, and x itself as αβ. With a little luck, one and only one of them should evaluate to 2α+2, and that becomes our αβ.

x2 multiply out substitute
α2 = 2
β2 = α+1
substitute
αβ = x
(1)2 = 1 = 1 = 1
(2)2 = 1 = 1 = 1
(α)2 = α2 = 2 = 2
(α+1)2 = α2+2α+1 = 2α = 2α
(α+2)2 = α2+α+1 = α = α
(2α)2 = α2 = 2 = 2
(2α+1)2 = α2+α+1 = α = α
(2α+2)2 = α2+2α+1 = 2α = 2α
(β)2 = β2 = α+1 = α+1
(β+1)2 = β2+2β+1 = 2β+α+2 = 2β+α+2
(β+2)2 = β2+β+1 = β+α+2 = β+α+2
(β+α)2 = β2+2βα+α2 = 2βα+α = 2β
(β+α+1)2 = β2+2βα+2β+α2+2α+1 = 2βα+2β+1 = β+2α
(β+α+2)2 = β2+2βα+β+α2+α+1 = 2βα+β+2α+1 = α+2
(β+2α)2 = β2+βα+α2 = βα+α = β
(β+2α+1)2 = β2+βα+2β+α2+α+1 = βα+2β+2α+1 = α+2
(β+2α+2)2 = β2+βα+β+α2+2α+1 = βα+β+1 = 2β+2α
(2β)2 = β2 = α+1 = α+1
(2β+1)2 = β2+β+1 = β+α+2 = β+α+2
(2β+2)2 = β2+2β+1 = 2β+α+2 = 2β+α+2
(2β+α)2 = β2+βα+α2 = βα+α = 2β+2α
(2β+α+1)2 = β2+βα+β+α2+2α+1 = βα+β+1 = α+2
(2β+α+2)2 = β2+βα+2β+α2+α+1 = βα+2β+2α+1 = β
(2β+2α)2 = β2+2βα+α2 = 2βα+α = β+2α
(2β+2α+1)2 = β2+2βα+β+α2+α+1 = 2βα+β+2α+1 = 2β
(2β+2α+2)2 = β2+2βα+2β+α2+2α+1 = <βα+2β+1 = α+2

Barp! You fail it! None of our values work as αβ when α2-2=0 and β2-( α+1 )= 0

Ok. At this point I have to conclude that perhaps you cannot freely choose your polynomials. But … I rather got the impression that you could. Brett?

Advertisements

4 Responses to Constructing finite fields.

  1. BrettW says:

    Ah, I get it. So when you extend GF(3) by an irreducible quadratic you get GF(3^2). If you extend GF(3^2) by an irreducible quadratic (defined over GF(3^2)), then you get GF(3^4), not GF(3^3).

    Therefore you don’t need to try to reduce the 81 elements down to 27. Elements of GF(3^4) are a + b*beta where both a and b are of the form c + d*alpha.

    So to answer your question, alpha*beta equals… alpha*beta! :) Commendable work though on observing squares on the diagonal (I hadn’t thought of doing it that way).

    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). Same goes for GF(27) – find an irreducible cubic and repeat the mantra.

    • Paul Murray says:

      Well – inspecting the diagonal is how a programmer approaches the job: forget this business of “proving” that your polynomial is irreducible; instead, just ask your long-suffering machine to do a brute force computation and put it somewhere where there’s a nice cool breeze overnight. It doesn’t scale to genuinely big numbers, of course.

      Now, we can get GF(p), GF(p^2), GF(p^4), GF(p^8) … GF(p^2^x) using the “find a square” method. To a programmer, this suggests a way of doing it for any n: treat n as a binary number, and add the bits.

      Say we want GF(p^22). 22 is 16+4+2, so we build GF(p^16), GF(p^4), and GF(p^2) in four steps using the quadratic method. Then (somehow!) combine the three fields into a combined field of the correct size.

      However … I kinda feel this won’t work – that “combining” GF(81) and GF(9) to get GF(729) can’t be done easily, because the size of the multiplicative group is p^n-1 and the factors of that might be anything. If 2^n-1 just happened to be prime, the multiplicative group will have to be the cyclic group, and nothing will “combine” to give that. That’s kind of the whole point – it’s exactly that that makes finite fields hard and interesting: there’s only one multiplicative part that works, and you don’t know what shape it might be until you look.

      Meh. I get the point on which I misunderstood your post – I need to look for a cubic over Z(3).

      It’s nice to note that ab was actually a basis of my GF(81), and so it shouldn’t have been expressible as a linear combination of 1, alpha, and beta, which means that my finding that it couldn’t be done was correct.

    • Paul Murray says:

      Note also that if you keep extending by this method, then you get the number of basis vectors that you’d expect.

      Say we extend GF(3) with α, then GF(9) with β, then GF(81) with γ. Our result is GF(3^8), so we need 8 basis vectors, right?

      No problem:

       1*1*1
       α*1*1
       1*β*1
       α*β*1
       1*1*γ
       α*1*γ
       1*β*γ
       α*β*γ
      

      Works out fine.

      • BrettW says:

        Doing arithmetic by building up field by field is complicated. It’s significantly easier to go from GF(p) to GF(p^n) via an irreducible polynomial of degree n.

        In any case, I think you’re getting the hang of this. :)

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: