# OK to past

# PART 1: MaxPer() PROCEDURE:
# -----------------------

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;
	return ret;
end:

for d from 3 to 10 do
	print(evalb(MaxPer(d, x) = WisW(d, x)[4]));
od;

# PART 2 - qPols(), qPolsE(), qIsPr(), qWisW(), qMaxPer() PROCEDURES:
# -----------------------

qPols:=proc(q,x,d) local S,s:
	option remember;

	if d=0 then
		return {1};
	fi;

	S:=qPols(q,x,d-1);
	return 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);
	return {seq(s+x^d mod q, s in S)};
end;

qIsIr:=proc(q,P)
	option remember;
	return 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;

	return true; 
end:

qWisW:=proc(q,d,x) local S,s, Si, Sp, Sip, Sne:
	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:
	return [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;
	return ret;
end:

for d from 3 to 5 do
	print(evalb(qMaxPer(3, d, x) = qWisW(3, d, x)[4]));
od;