[GAP Forum] Finite fields

[Richard Barraclough]

> hi,
> I
> I have some doubts on finite fields. Can anyone answer the following question?
> 
> we wish to encode the message using  F32... Define the cumulative degree of a
> polynomial to be the sum of degrees of its monomials.
> 
> a)How many irreducible polynomials of degree 5 over Z/2Z are there?
> what are they?

You can use GAP to find this out easily,
F := FiniteField(2);
x := Indeterminate(F);
V := FullRowSpace(F,5);
for v in V do
  f := x^5;
  for i in [1..5] do
    f := f + v[i]*x^(i-1);
  od;
  if IsIrreducible(f) then
    Print(f,"\n");
  fi;
od;


> 
> 
> b)
> Let Y be a root of the irreducible polynomial of degree 5 of lowest cumulative
> degree. Then { 1,Y,Y^2,Y^3,Y^4} forms a basis for F32 over Z/2Z. Writing each
> element  of F32 as a 5 tuple with respect to this basis, find all the powers
> of Y.

Lets say our polynomial is x^5 + x^3 + 1
So
1   -> 10000
Y   -> 01000
Y^4 -> 00001
Y^5 -> 10010
Let A := [[0,0,0,0,0],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0]]*Z(2);
When we multiply a vector by A it shifts all co-ordinates to the right and
fills the left with zeros, i.e., bit shift.
So multiplying a vector by A is the same as multiplying the corresponding
F32 number by Y except that we have to sort out what happens when our
vectors overflow at the right.
If the 5th co-ordinate (the one corresponding to Y^4) is 1, then we shall
add 10010 after bit shifting, because 10010 corresponds to Y^5.
So,
Y^6 = (Y^5)A = 01001
Y^7 = (Y^6)A + 10010 = 10110
Y^8 = (Y^7)A = 01011
Y^9 = (Y^8)A + 10010 = 10111
Y^10 = (Y^9)A + 10010 = 11001
etc.

This is an easy way to build a lookup table for encoding/decoding.

> c) We encode message (numbers between 0 and 31) by raising it Y to that power
> and then returning the five-bit binary representation we get when writing this
> element as a 5-tuple with respect to {1,Y,Y^2,Y^3,Y^4}.If 19 is the result
> then what number was initially sent?.

19 -> 11001 which happens to correspond to Y^10.



Wouldn't it be OK just to send the un-encoded message? I can't see how this
coding can correct any errors.


Regards,
Richard Barraclough