Recently I've got a homework of Decoding Theory, which I guess it's one of branches of advanced algebra. But I can barely understand what my professor means about this assignment. Is it something about finite fields? Can somebody explain it for me? :Write a GAP program and compute the following:

Take p = 2, 3, 5
Take a primitive element z of GF(p^4)

1. Make the list L of ordered pairs [i,j], i=1..p^m-1, so that z^i + 1 = z^j.

2. Make the list M1 of ordered pairs [i, f_i], i=1..p^m-1, so that f_i is the minimal polynomial of z^i over GF(p).

3. Make the list M2 of ordered pairs [i, g_i], i=1..p^m-1, so that g_i is the minimal polynomial of z^i over GF(p^2).

Do it on a computer.

Hi,
Do you have experience in GAP programming? If not, I'd say the assignment is entirely unreasonable. But GAP really presupposes a pretty good knowledge of abstract algebra, groups in particular (G in GAP stands for groups). The notation in your question is GAP syntax.

First, GF(p^n) is the finite field with p^n elements where p is a prime. A primitive element of this field is an element z such that every non-zero element of the field is a power of z. GAP is very happy to find you such a z. The first question is then an easy programming exercise to create the given list.

Next the minimum polynomial of an element a in a field F over a field K is a monic irreducible polynomial p(x) with coefficients in K such that p(a)=0. Again GAP will compute the list of all irreducible polynomials from a list of field elements. For both questions 2 and 3, F is GF(p^4). In 2, K is GF(p) and in 3, K = GF(p^2).

I don't know if this is what you wanted. It seems to me without a basic knowledge of finite fields, you have no idea what you're computing, even if you successfully get GAP to do it for you.

johng,
For this assignment, I studied these basic notions about finite fields. Not very familiar, but I know what they mean know. However, even with these notions in mind, I still don't know how to write the program. Sorry, I have no knowledge about GAP. Tried to read its manual, but I still don't get it. Can GAP find a primitive element for GF(p^4)? If yes, how?

Hi Rita,
I am an "experienced" programmer, but I must confess I've never written a GAP program. I've just read about it. It seems to me GAP is really meant as a research tool in various areas of algebra. So I have no idea how primitive roots are found. However, the problem of primitive roots even in GF(p) is quite hard. As far as I know, there is no general algorithm to produce one. An exhaustive search is about the only general procedure. So for large primes, it is extremely hard.

Since your problem involves very small numbers (your biggest field has only 625 elements), once you have a concrete representation of the field, exhaustive search will quickly produce a primitive root.

I stand by my original comment. I think your assignment is too hard.

Dear johng,
Good news is that I've figured out how to use GAP to compute all these values, including primitive elements and minimal polynomials in each question. The thing is...for instance, take p=2, in question 1, for each i=1,2,3,...,p^m-1, I can compute z as well as each pair [i,j], but separately. It seems like I'm using GAP to "compute" each value of the problem. Is it a "program" as my professor asked? Or is there a way to write a program "for all i," then it'd compute automatically?(That seems a right definition of "program" to me.)

For example, as I focus on the second question, I seem writing each output:
F:=GF(2^4);
GF(2^4)
z:=PrimitiveElement(F);
Z(2^4)
f_1:=MinimalPolynomial(GF(2),z);
x_1^4+x_1+Z(2)^0
f_2:=MinimalPolynomial(GF(2),z^2);
x_1^4+x_1+Z(2)^0
f_3:=MinimalPolynomial(GF(2),z^3);
x_1^4+x_1^3+x_1^2+x_1+Z(2)^0
f_4:=MinimalPolynomial(GF(2),z^4);
x_1^4+x_1+Z(2)^0
f_5:=MinimalPolynomial(GF(2),z^5);
x_1^2+x_1+Z(2)^0
f_6:=MinimalPolynomial(GF(2),z^6);
x_1^4+x_1^3+x_1^2+x_1+Z(2)^0
f_7:=MinimalPolynomial(GF(2),z^7);
x_1^4+x_1^3+Z(2)^0
f_8:=MinimalPolynomial(GF(2),z^8);
x_1^4+x_1+Z(2)^0
.
.
.
.
I guess it's not a program. Do you know what I mean?

Hi,
As I said before, I've never written a GAP program and still haven't. I think what you mean is you want to write a loop that does all the calculations. In GAP, the fundamental data structure is the list. So for your first question, you need to construct the list L in a loop (I guessed that m=(p^4-1)/2). I haven't even downloaded GAP, but from what I read, the following is close to what you want:

Code:
p:=2;
m:=(p^4-1)/2;
F:=GF(p,4);
z:=PrimitiveElement(F);
L:=[ ]; #empty list
i:=1;
while i<=m do
Add(L,[i,LogFFE(z^i + 1,z)];  # i.e., j=LogFFE(z^i+1,z) is the power with z^j=z^i +1
i:=i+1;
od;
L; # display the list L
You can try the above code and see what happens. I really don't want to get into GAP programming.