# OK to post

# PART 2, FINDING NUMBER OF IRREDUCIBLE POLYNOMIALS:
# -----------------------

# q=2:
# for degree=1..8, we get the sequence 2, 1, 2, 3, 6, 9, 18, 30
# putting this into OEIS, we find that the 20th term is 13178

# q=5:
# for degree=1..4, we get the sequence 5, 10, 40, 150
# putting this into OEIS, we find that the 20th term is 4768371093720

# q=7:
# for degree=1..4, we get the sequence 7, 21, 112, 588
# OEIS only has up to the 19th term, which is 599941851861744

# q=11
# for degree 1..4, we get the sequence 11, 55, 440, 3630
# OEIS only has up to the 17th term, which is 29732178147017280

# PART 3: MulTable() PROCEDURE:
# -----------------------

MulTable:=proc(q,f,x) local d,F,i,j,T:
	d:=degree(f,x);
	F:=AllPols(q,d-1,x) minus {0};

	T:=[[0$(nops(F)+1)]$(nops(F)+1)];

	for i from 1 to nops(F) do:
		T[1][i+1]:=F[i];
		T[i+1][1]:=F[i];
	od;

	for i from 1 to nops(F) do:
		for j from 1 to nops(F) do:
			T[i+1][j+1]:=Mul(q,F[i],F[j],x,f);
		od;
	od;

	return T;
end:

############################################################## OLD CODE ##############################################################

#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:

#Added after class
#MonicPols(q,d,x): all the monic poynomials of degree d over GF(q). Try:
#MonicPols(3,4,x);
MonicPols:=proc(q,d,x) local S,s:
S:=AllPols(q,d-1,x):
{seq(x^d+s, 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:

HD:=proc(u,v) local i,co:
co:=0:
for i from 1 to nops(u) do
  if u[i]<>v[i] then
      co:=co+1:
  fi:
od:
co:
end:

############################################################## END OLD CODE ##############################################################

# PART 4: VERIFYING FIELD/NOT FIELD:
# -----------------------

# x^3+2*x+1 is irreducible, so we expect a multiplicitave inverse to exist (1 in each row)
T1:=MulTable(3,x^3+2*x+1,x):
{seq(member(1,T1[i]), i=1..nops(T1))}; # and indeed this is true

# x^3+x is reducible [(x^2+1)(x)], so we expect to find a row without a multiplicitave inverse
T2:=MulTable(3,x^3+x,x):
{seq(member(1,T2[i]), i=1..nops(T2))}; # and indeed there is a row without a 1

# PART 5: NearestNeighbor() PROCEDURE:
# -----------------------

NearestNeighbor:=proc(C,v) local minD,nearest,c:
	minD:=HD(v,C[1]);
	nearest:=C[1];

	for c in C do:
		if HD(v,c)<minD then
			minD:=HD(v,c);
			nearest:=c;
		fi;
	od;

	return nearest;
end;