#1. Read and Understand pp141-150

#2. 
#--DEPENDENCIES
#AllPols(q,d,x): the set of all the polynomials of degree <=d in x over GF(q) (q is a prime)
AllPols:=proc(q,d,x) local S,s,i:
option remember:
if d=0 then
 RETURN({seq(i,i=0..q-1)}):
fi:
S:=AllPols(q,d-1,x):
{seq(seq(s+i*x^d,i=0..q-1), s in S)}:
end:

#Mul(q,P1,P2,x,f): P1*P2 mod q mod f
Mul:=proc(q, P1, P2, x, f):
rem(P1*P2, f, x) mod q:
end:

#Irreds(q,d,x): all monic  irreducible polynomials in GF(q)[x] of #degree d
Irreds:=proc(q,d,x) local d1,S,S1,S2,s1,s2:

S:=MonicPols(q,d,x):

for d1 from 1 to d-1 do
 S1:=MonicPols(q,d1,x):
 S2:=MonicPols(q,d-d1,x):
 S:=S minus {seq(seq(expand(s1*s2) mod q, s1 in S1),s2 in S2)}:
od:
S:
end:

#--NEW WORK

S:={2,5,7,11};
#note: replace 5 by 9 in the for loop below to obtain the desired #result. for computational speed we stop at 5 here 

for q in S do
for i from 1 to 8 do
print("The number of irreducibles of degree", i-1,"is",nops(Irreds(q,i,x))):
od:
od:
 
#These correspond to the following OEIS sequences:
#GF(2): A000079
#GF(5): A001692
#GF(7): A212486
#GF(11): A218336


#3---------------MulTable(q,f,x)

MulTable:=proc(q,f,x) local table ,i,j, GF, row:
GF:=AllPols(q,degree(f)-1,x);
table:=[];
 #because 1 is included in GF, we will get the polynomials themselves #on the first row and column, as wanted

for i in GF do 
row:=[];
 for j in GF do
	row:=[op(row), rem(i*j, f,x) mod q];
od:
table:=[op(table), row];
od:
table;

end:


#4-------------------Mul Table of irreducible&reducible Polynomials
#Also verify that it is a field by checking that every row of the #table has a 1 in it. 

f:=x^2+x+1;
g:=x^3+x^2+x;

A:=MulTable(3,f,x);
B:=MulTable(3,g,x);


FieldCheck:=proc(T) local rowsetn, rowlength, inrow, k, n:

rowlength:=nops(T[1]);
#check to see of each row has a 1 in it

for n from 1 to nops(T) do
rowsetn:=tolist(seq(T[n][k], k=1..rowlength));
inrow:=member(1, rowsetn):
if inrow=true then print("this row contains 1");
else print("this row does not contain 1");
fi:
od:




end:


FieldCheck(A);
#FieldCheck(B);