# OK to post homework
# Alex Varjabedian, 21-Mar-2024, Homework 17

Help := proc() print(`MaxPer(d, x)\nqPols(q,x,d)\nqPolsE(q,x,d)\nqIsPr(q,P,x)\nqWisW(q,d,x)\nqMaxPer(q,d,x)`) end:

IsPer:=proc(L,t) local i:
if {seq(L[i]-L[i+t],i=1..nops(L)-t)}={0} then
  true:
else
 false:
fi:
end:

FindPer:=proc(L) local t:
for t from 1 to trunc(nops(L)/2) while not IsPer(L,t) do od:
if t=trunc(nops(L)/2)+1 then
RETURN(FAIL):
else
 RETURN(t):
fi:
end:

qSR:=proc(q,INI,L,n) local r,i,M,ng:
r:=nops(L):
if nops(INI)<>L[-1][2] then
 RETURN(FAIL):
fi:
if not (sort(INI)[-1] < q and sort(INI)[1] >= 0) then
 RETURN(FAIL):
fi:
if not (type(L, list) and {seq(type(L[i], list), i=1..nops(L))} = {true} and {seq(type(L[i][1], posint), i=1..nops(L))} = {true} and {seq(type(L[i][2], posint), i=1..nops(L))} = {true} and sort([seq(L[i][1], i=1..nops(L))])[-1] < q and sort([seq(L[i][1], i=1..nops(L))])[1] >= 0 and sort([seq(L[i][2], i=1..nops(L))]) = [seq(L[i][2], i=1..nops(L))]) then
   RETURN(FAIL):
fi:
if not type(n,posint) then
     RETURN(FAIL):
fi:

M:=INI:

while(nops(M))<n do
 ng:=add(L[i][1]*M[-L[i][2]],i=1..r) mod q:
 M:=[op(M),ng]:
od:
M:

end:

Pols:=proc(x,d) local S,s:
option remember:
if d=0 then
 RETURN({1}):
fi:
S:=Pols(x,d-1):
S union {seq(s+x^d,s in S)}:
end:

PolsE:=proc(x,d) local S,s:
S:=Pols(x,d-1):
{seq(s+x^d, s in S)}:
end:

########################
# -------------------- #
# PART 1 - MaxPer(d,x) #
# -------------------- #
########################

print(`PART 1`);

PolToList := proc(P, x) local c:
[seq(c mod 2, c in coeffs(P, x))]:
end:

MaxPer := proc(d, x) local ret, i, P:
ret := {}:
for P in PolsE(x, d) do
 if FindPer(qSR(2, [1, 0$(d-1)], PolToList(P, x), nops(PolToList(P, x)))) = 2^d - 1 then
  ret := ret union {P}:
 fi:
od:
ret:
end:

# Testing

for d from 3 to 10 do
 printf("MaxPer(%a, x) = WisW(%a, x)[4]? %a\n", d, d, evalb(MaxPer(d, x) = WisW(d, x)[4]));
od:

####################################################################################
# -------------------------------------------------------------------------------- #
# PART 2 - qPols(q,x,d), qPolsE(q,x,d), qIsPr(q,P,x), qWisW(q,d,x), qMaxPer(q,d,x) #
# -------------------------------------------------------------------------------- #
####################################################################################

print(`PART 2`);

qPols:=proc(q,x,d) local S,s:
option remember:
if d=0 then
 RETURN({1}):
fi:
S:=qPols(q,x,d-1):
S union {seq(s+x^d mod q,s in S)}:
end:

qPolsE:=proc(q,x,d) local S,s:
S:=qPols(q,x,d-1):
{seq(s+x^d mod q, s in S)}:
end:

qIsIr:=proc(q,P)
option remember:
evalb(Factor(P) mod q=P mod q):
end:

qIsPr:=proc(q,P,x) local d,m,i:
option remember:
d:=degree(P,x):
m:=2^d-1:
 for i from 1 to m-1 do
   if rem(x^i,P,x) mod q<>0 then
     RETURN(false):
   fi:
od:
if rem(x^m,P,x) mod q=0 then
   print(`Something bad happened, Cocks' aritcle is wrong!, or more likely (according to George)`):
   print(`we messed up`):
    RETURN(FAIL):
fi:
true: 
end:

qWisW:=proc(q,d,x) local S,s, Si, Sp, Sip, Sne:
#Si:=set of pol. of degree d (mod 2) that are irreducible but NOT primitive
#Sp:=set of pol. of degree d (mod 2) that are NOT irreducible but  primitive
#Sip:=set of pol. of degree d (mod 2) that are BOTH irreducible and  primitive
#Sne= neither
S:=qPolsE(q,x,d):
Si:={}: Sp:={}: Sip:={}: Sne:={}:

for s in S do
 if qIsIr(q,s) and not qIsPr(q,s,x) then
   Si:=Si union {s}:
  elif  not qIsIr(q,s) and  qIsPr(q,s,x) then
    Sp:=Sp union {s}:
  elif   qIsIr(q,s) and  qIsPr(q,s,x) then
    Sip:=Sip union {s}:
   else
     Sne:=Sne union {s}:
  fi:
 od:

[Sne,Si,Sp,Sip]:
end:

qPolToList := proc(q, P, x) local c:
[seq(c mod q, c in coeffs(P, x))]:
end:

qMaxPer := proc(q, d, x) local ret, i, P:
ret := {}:
for P in PolsE(x, d) do
 if FindPer(qSR(q, [1, 0$(d-1)], qPolToList(q, P, x), nops(qPolToList(q, P, x)))) = 2^d - 1 then
  ret := ret union {P}:
 fi:
od:
ret:
end:

# Testing

for d from 3 to 5 do
 printf("qMaxPer(3, %a, x) = qWisW(3, %a, x)[4]? %a\n", d, d, evalb(qMaxPer(3, d, x) = qWisW(3, d, x)[4]));
od: