The time before that, we saw that for each prime p, there is a finite field Fp, consisting of the set {0,1,...,p-1}, with the arithmetic operations carried out modulo p.

This week we're going to bring these two ideas together, and look at algebraic extensions of Fp.

Algebraic extensions of Fp work just the same way as algebraic extensions of Q. First, find an irreducible polynomial over the base field K - that means, a polynomial f(x) in K[x], which can't be expressed as f(x) = g(x) * h(x), for g(x), h(x) in K[x] of lower degree. For example, whenever d is an element of K without a square root in K, then x^2-d is irreducible. Then, form the quotient ring K[x]/

For example, in F3, and also in F5, there is no square root of 2. So we can form the fields F3(sqrt2) or F5(sqrt2). We need to be a bit careful about terminology. 2 in F3, 2 in F5, and 2 in Q, are all different things - consequently sqrt2 in F3, in F5, and in Q are all different things. We mustn't make the mistake of thinking they're the same thing.

We saw last time that Q(sqrt2) consists of { a + b sqrt2 | a, b in Q }. Similarly, F5(sqrt2) consists of { a + b sqrt2 | a, b in F5 }. In particular, it follows that F5(sqrt2) has 25 elements. In general, a simple algebraic extension of Fp will have p^n elements, where n is the degree of the irreducible polynomial.

Over Q, we were able to form the fields Q(sqrt2), Q(sqrt3), Q(i), and so on. Somewhat surprisingly, over Fp, it turns out that any algebraic extension of degree n is isomorphic to any other. For example, F5(sqrt2) is isomorphic to F5(sqrt3). For this reason, we typically just talk about F25 (meaning, the field with 25 elements) - or in general, Fq, where q = p^n is a prime power.

However, in order to do arithmetic in F25 or in Fq, we clearly need to have some particular irreducible polynomial in mind. Otherwise, we won't know whether to reduce x^2 to 2, or to 3, for example. So for each p, n, we need to agree on an irreducible polynomial of degree n over Fp. There doesn't appear to be any natural way to choose, so an artificial way to choose has been devised, called the Conway polynomials.

So, using a little phantom type trickery as before, here are the first few finite fields of prime power order, as defined in the HaskellForMaths library:

data ConwayF4

instance PolynomialAsType F2 ConwayF4 where pvalue _ = convert $ x^2+x+1

type F4 = ExtensionField F2 ConwayF4

f4 = map Ext (polys 2 f2) :: [F4]

a4 = embed x :: F4

data ConwayF8

instance PolynomialAsType F2 ConwayF8 where pvalue _ = convert $ x^3+x+1

type F8 = ExtensionField F2 ConwayF8

f8 = map Ext (polys 3 f2) :: [F8]

a8 = embed x :: F8

data ConwayF9

instance PolynomialAsType F3 ConwayF9 where pvalue _ = convert $ x^2+2*x+2

type F9 = ExtensionField F3 ConwayF9

f9 = map Ext (polys 2 f3) :: [F9]

a9 = embed x :: F9

data ConwayF16

instance PolynomialAsType F2 ConwayF16 where pvalue _ = convert $ x^4+x+1

type F16 = ExtensionField F2 ConwayF16

f16 = map Ext (polys 4 f2) :: [F16]

a16 = embed x :: F16

data ConwayF25

instance PolynomialAsType F5 ConwayF25 where pvalue _ = convert $ x^2+4*x+2

type F25 = ExtensionField F5 ConwayF25

f25 = map Ext (polys 2 f5) :: [F25]

a25 = embed x :: F25

As we did with the fields Fp, we provide the functions f4, f8, f9, etc, which just return a list of the elements of the corresponding fields. a4, a8, a9 etc return the element that has been adjoined to the underlying field to make the extension field.

For example:

> f8

[0,a^2,a,a+a^2,1,1+a^2,1+a,1+a+a^2] :: [F8]

> a8 ^ 3

1+a :: F8

We can partially verify the claim that F25 = F5(sqrt2) = F5(sqrt3), by exhibiting square roots of 2 and 3 in F25:

> (2+a25)^2

2 :: F25

> (1+3*a25)^2

3 :: F25

Last time, I mentioned that extension fields can have automorphisms, without really spelling out what that means. Well, if L is an extension of K, then f is an automorphism of the extension if for a,b in L, c in K, f(a+b) = f(a)+f(b), f(a*b) = f(a)*f(b), etc, and f(c*a)= c*f(a). In other words, f(L) looks the same as L, viewed from K.

The finite fields Fq (q = p^n) have an automorphism called the Frobenius automorphism, defined by f(x)=x^p. For example:

> f9

[0,a,2a,1,1+a,1+2a,2,2+a,2+2a]

> map frobeniusAut f9

[0,1+2a,2+a,1,2+2a,a,2,2a,1+a]

Finally, a word about efficiency. The HaskellForMaths implementation of fields Fq is very natural from a mathematical point of view, but it isn't very efficient.

Firstly, we are working with polynomials with coefficients in Fp. To multiply two degree n polynomials together, we have to do O(n^2) additions and multiplications of coefficients. If the coefficients are in Fp, each one of these involves a (`mod` p) operation. It would be better to do the polynomial arithmetic over the integers, and only do the `mod` p at the end. We would then only have to do O(n) (`mod` p) operations.

Secondly, we could consider implementing the fields Fq using Zech logarithms instead.

Anyway, it doesn't matter too much for the moment, as I only want to use the finite fields to construct combinatorial structures. But sometime I might try to write a more efficient implementation.

Next time: finite geometries.

Hi,

ReplyDeletethanks for this very interesting library.

I think something's missing in Math/Algebra/Field/Extension :

> +set +t

> 1.4 :: Q

7/5

it :: Q

> 1.4 :: QSqrt3

*** Exception: Math/Algebra/Field/Extension.hs:116:0: No instance nor default method for class operation GHC.Real.fromRational

Hmm, thanks for pointing this out. When I added a definition for fromRational, I discovered a subtle bug in the code:

ReplyDelete> 1/5 :: QSqrt3

1

I now have fixes for both problems, which will be in the next release.