• CIRCA Home
  
  
• Members
  
  
• Pre-prints
  
  
• Library
  
  
• Annual Reports
  
  
• Seminars
  
  
• Conferences
  
  
• Research
  
  
• Publicity
  
  
• Pictures
  
  
• GAP
  
  
• Webmail

GAP Instructional Material

Return to Index

GAP code is shown like this.

[Press ?? to see GAP output]

You can also choose to see a page showing ALL GAP output.

Some theory

GAP knows that there is a unique finite field of order n = p^k for any prime p. It calls it GF(n). (This stands for Galois Field.)
GAP also knows that the multiplicative group of such a finite field is cyclic and it chooses a generator for this cyclic group which it calls Z(n). It then refers to the elements of the field as {0*Z(n), Z(n)⁰ , Z(n)¹, ... , Z(n)^n-2}. Note that Z(n)^n-1 = Z(n)⁰ is the multiplicative identity.
GAP supports all finite fields of order less than or equal to 2¹⁶ (= about 65000). Hence GF(3¹⁰), GF(5⁶), GF(7⁵), etc. and smaller fields are supported. All prime fields are supported, so GF(p) is supported even when p > 2¹⁶.

The finite field GF(11)

We can illustrate how this works with GF(11).

To create this field and name it F we use the command

F:= GF( 11 );      ??

One often calculates with the elements of this field as if they were integers { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } but GAP distinguishes between elements of GF(11) and integers. For example 0 is not an element of GF(11), so we get false if we test this

0 in F;      ??

In fact none of the integers { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } are elements of F.

The zero of F is given as follows

z:= Zero( F );      ??

z in F;      ??

and the multiplicative identity is

one:= One( F );      ??

one in F;      ??

We could denote the zero element by 0 One(F)

0*one in F;      ??

Now we have the elements of F by multiplying the integers { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } each by One(F)

for i in [0..10] do
 Print(i*one in F, "\n");
od;      ??

GAP chooses a generating element of the (cyclic) multiplicative group of the field as Z(11) and displays the elements as 0*Z(11), Z(11)^0, Z(11)^1, Z(11)^2, ... , Z(11)^9. In fact, for GF(11) the element "2" is denoted by Z(11)^1 or by Z(11). We could easily find this out

for i in [0..10] do
 if (i*one = Z(11)) then Print(i, "\n"); fi;
od;      ??

There is, however, a better way to convert elements of GF(11) written in GAP notation back to 0, 1, 2, ... using IntFFE (which stands for Integer form of a Finite Field Element).

IntFFE(Z(11));      ??

In general we can convert all the elements of GF(11) back to corresponding integers since 11 is prime.

for i in [0..10] do
 Print(i*one," is ", IntFFE(i*one), "\n");
od;      ??

We can now do calculations in F as follows. All the following calculate the multiplicative inverse of Z(11), which is the same as the multiplicative inverse of "2".

Inverse( Z(11) );      ??
2^(-1)*one;      ??
Z( 11 )^(-1);      ??
Inverse( 2*one );      ??

We can add elements of F

Z(11)+Z(11)^2;      ??

A moment's thought shows that this is right: 2 + 4 = 6 is the inverse of 2 in GF(11).

Again as above, several different commands will give us the additive inverse (i.e. negative) of Z(11).

AdditiveInverse( Z(11) );      ??
-2*one;      ??
-Z(11);      ??
AdditiveInverse(2*one);      ??

Now the non-zero elements of F have multiplicative orders which can be calculated as follows

Order( Z(11) );      ??

or for all the elements

for i in [1..10] do
 Print(i," order ", Order(i*one), "\n");
od;      ??

We can see that there are four generators of the multiplicative group of GF(11).

Irreducible polynomials over the field GF(3)

We begin by setting up our field GF(3).

F:= GF( 3 );      ??

one:= One( F );      ??

We need an indeterminate in order to look at polynomials over GF(3). We'll use x.

x:= Indeterminate(F,"x");      ??

We now set up an empty list and add irreducible polynomials (ones which cannot be written as a product of polynomials of lower degree) to the list. We examine all polynomials of degree up to 4, finding whether they are irreducible and if so add them to the list. GAP does not give any ouut here.

list:= [];
for i in F do
 for j in F do
  for k in F do
   for l in F do
    for m in F do
     if IsIrreducibleRingElement(i*x^4+j*x^3+k*x^2+l*x+m) then
      Add(list, i*x^4+j*x^3+k*x^2+l*x+m);
     fi;
    od;
   od;
  od;
 od;
od;

To see how many irreducible polynomials there are of degree up to 4 over GF(3) we need only look now at the length of our list.

Length(list);      ??

There are 64 of them.

Suppose we want to find how many polynomials of degree up to 4 over GF(3) have one factor, how many have two factors, etc.

list:= [ [],[],[],[] ];
for i in F do
 for j in F do
  for k in F do
   for l in F do
    for m in F do
     num:= Length(Factors(i*x^4+j*x^3+k*x^2+l*x+m));
     Add(list[num], i*x^4+j*x^3+k*x^2+l*x+m);
    od;
   od;
  od;
 od;
od;

Let us see how many there are of each length

for i in [1..4] do
 Print("There are ", Length(list[i]), " with ", i," factors", "\n");
od;      ??

Notice there were 64 irreducible polynomials but 67 polynomials with a single factor. This is because 0, 1, -1 are polynomials with a single factor but are not irreducible.

The total should be 3⁵ - let us check

Sum(List([1..4], i -> Length(list[i])));      ??

The finite field GF(4)

We input the field of 4 elements

F:= GF( 4 );      ??
one:= One(GF( 4 ));      ??

Let us see how GAP represents its elements

Elements( F );      ??

Elements of GF(4) are roots of polynomials over GF(2) and so of course not all the elements of GF(4) have representations as integers. We can only apply IntFFE to the elements of the prime field of GF(4) to get representations of them as integers.

IntFFE(one);      ??

Applying IntFFE to elements not in the prime field produces an error.

IntFFE(Z( 4 ));      ??

Now the prime field of F should be GF(2)

PrimeField( F );      ??

and F should have degree 2 over its prime subfield

DegreeOverPrimeField( F );      ??

F must be defined by an irreducible polynomial over its prime subfield. Let us find the one that GAP is using. Note that GAP calls the indeterminate x₁ .

DefiningPolynomial( F );      ??

To convince ourselves that it is irreducible, look at its irreducible factors.

Factors(DefiningPolynomial( F ));      ??

The generator of F, which will be Z(4), should be a root of the defining polynomial

RootOfDefiningPolynomial( F );      ??

Now we check that Z(4) is a root of 1 + x + x²

one + Z(4) + Z(4)^2;      ??

The finite field GF( 2⁴ )

We examine exactly the same features of GF( 2⁴ ) as for GF( 4 )

F:= GF( 2^4 );      ??
one:= One(GF( 2^4 ));      ??
Elements( F );      ??

Now the prime field of F should be GF(2) and F should have degree 4 over GF(2)

PrimeField( F );      ??

DegreeOverPrimeField( F );      ??

The defining polynomial in this case is

DefiningPolynomial( F );      ??

which, of course, is irreducible

Factors(DefiningPolynomial( F ));      ??

Its root will be Z(2⁴)

RootOfDefiningPolynomial( F );      ??

and of course Z(2⁴) satisfies this irreducible polynomial

one + Z(2^4) + Z(2^4)^4;      ??

But there are other irreducible polynomials of degree 4 over GF(2) that we could use to define a field with 16 elements. Let us use 1 + x³ + x⁴.

x:= Indeterminate(GF(2), "x");      ??

FF:= GF( 2, 1 + x^3 + x^4 );      ??

Now the defining polynomial will be 1 + x³ + x⁴ because we have defined it to be this.

DefiningPolynomial( FF );      ??

The root of the defining polynomial will not now be Z(2⁴ ) of course. What is it?

RootOfDefiningPolynomial( FF );      ??

The elements of FF are in fact the same 16 elements that GAP has defines in its version of GF(2⁴).

FF=F;      ??

Note the following important fact relating to finite fields.
GF(pⁿ) is actually a subset of GF(p²ⁿ). So

IsSubsetSet(Elements(GF( 16 )), Elements(GF( 4) ));      ??

will return "true". Of course GF(4) is not contained in GF(8) so

IsSubsetSet(Elements(GF( 8 )), Elements(GF( 4 )));      ??

will return "false".

A problem about trinomials over GF(2)

Suppose we wanted to define GF(2ⁿ) by means of a trinomial over GF(2). To do this requires there to be an irreducible polynomial of the form 1 + xⁱ + xⁿ over GF(2) for every n. Let us test whether this looks likely. First set up a polynomial ring over GF(2).

F:= GF( 2 );;
R:= PolynomialRing(F, 1);;
indets:= IndeterminatesOfPolynomialRing(R);;
x:= indets[1];;
one:= One(R);;

for n in [2..20] do
 for i in [1..n-1] do
  p:= x^n + x^i + one;
  if IsIrreducibleRingElement(p) then
   Print("Degree ", n, " has irreducible ", p, "\n");
   break;
  fi;
 od;
od;      ??

We see that there is no such polynomial for degree 8, 13, 16, 19, ...

Perhaps we should print out the numbers for which there is no irreducible trinomial. We will use the fact that if 1 + xⁱ + xⁿ is irreducible then so is 1 + x^(n-i) + xⁿ. So, for n > 2, we will never find that the first irreducible we reach is beyond 1 + x^m + xⁿ where m = Int(n/2), the integer part of n/2. This observation speeds up the calculation.

for n in [3..50] do
 for i in [1..Int(n/2)+1] do
  p:= x^n + x^i + one;
  if IsIrreducibleRingElement(p) then
   break;
  fi;
 od;
 if (i = Int(n/2+1)) then
  Print("Degree ", n, " has no irreducible trinomial", "\n");
 fi;
od;      ??

We have used a break; statement which makes GAP jump out of its loop. If there are several loops inside one another, it will just jump out of the innermost one.

It seems as if there is no irreducible trinomial for n a multiple of 8. Is this true? Perhaps we should look for more evidence

for n in 8*[1..20] do
 for i in [1..Int(n/2)] do
  p:= x^n + x^i + one;
  if IsIrreducibleRingElement(p) then
   break;
  fi;
 od;
 if (i = Int(n/2)) then Print("Degree ", n,
  " has no irreducible trinomial", "\n");
 fi;
od;      ??

So these multiples of 8 all have no irreducible trinomial. Must be worth trying to prove a theorem.

Can you spot any other likely theorems?

• Return to GAP Instructional Material Index page
• See page showing ALL GAP output

Home   |   Members   |   Pre-prints   |   Library   |   Reports   |   Seminars   |   Conferences   |   Research   |   Publicity   |  Pictures   |   GAP   |   Webmail