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):
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:
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
(αβ)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 αβ.
α2 = 2
β2 = α+1
αβ = 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?