#George Spahn
#2/25/2024
#OK TO POST


#2

#seq(nops(Irreds(2,i,x)),i=2..8)  
#1, 2, 3, 6, 9, 18, 30
#A001037
# A(20)=52377

#seq(nops(Irreds(5,i,x)),i=2..8)  
#10, 40, 150, 624, 2580, 11160, 48750
#A001692
# A(20)=4768371093720

#seq(nops(Irreds(7,i,x)),i=2..6)  
#21, 112, 588, 3360, 19544
#A001693
# A(20)=3989613300756720

#seq(nops(Irreds(11,i,x)),i=2..5)  
#55, 440, 3630, 32208
#A032166
# A(20)=33637499745331128504

MulTable := proc(q,f,x)
local P,T,i,j:
P := AllPols(q,degree(f)-1,x):
for i in P do for j in P do
T[i,j] := Mul(q,i,j,x,f):
od: od:
op(T):
end:

#4 f = x^3 + x^2 + 2
# ouput too big to be included but it looks like a field
# f = x^3
# (x^2)*x = 0




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


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

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