#OK to post homework
#GLORIA LIU, Mar 23 2024, Assignment 17

read `C17.txt`:
read `hw16GloriaLiu.txt`:

#=====================================#
#1. Write a procedure
#MaxPer(d,x)
#that inputs a positive integer d and putputs the set of all polynomials of degree d in x (mod 2) 
#that correspond (via the recurrence) to sequences of period 2^d-1 with initial condition INI=[1,0$
#(d-1)] [Hint: you first need a litte macro PolToList(P,x), in order to use FindPer(SR(INI,L,n))]

#Is MaxPer(d,x)=WisW(d,x)[4] for all d from 3 to 10?

PolToList:=proc(P,x) local L,i,n,d:
L:=[]:
n:=degree(P,x):
for d from 1 to n do
 if coeff(P,x,d) mod 2=1 then
  L:=[op(L), d]:
 fi:
od:
L:
end:

MaxPer:=proc(d,x) local INI,pols,p,L,per,result,n:
INI:=[1,0$(d-1)]:
pols:=PolsE(x,d):
n:=2^(d+1):
result:={}:
for p in pols do
 L:=PolToList(p,x):
 #print(L);
 #print(SR(INI,L,n));
 #print(FindPer(SR(INI,L,n)));
 per:=FindPer(SR(INI,L,n)):
 if per=2^d - 1 then
  result:=result union {p}:
 fi:
od:
result:
end:

#Yes MaxPer(d,x)=WisW(d,x)[4] for all d from 3 to 10

#=====================================#
#2. Write procedures
#qPols(q,x,d), qPolsE(q,x,d), qIsPr(q,P,x), qWisW(q,d,x), and qMaxPer(q,d,x)
#that generalize to GF(q) from GF(2). Is
#qMaxPer(3,d,x)=qWisW(3,d,x)[4] for all d from 3 to 5?

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

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

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

qIsPr:=proc(q,P,x) local m,d,i:
option remember:
d:=degree(P,x):
m:=q^d-1:
for i from 1 to m-1 do
 if rem(x^i,P,x) mod q = 1 then
   RETURN(false):
 fi:
od:
if rem(x^m,P,x) mod q<>1 then print(rem(x^m,P,x) mod q); print(P); RETURN(FAIL): fi:
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
 #print(s);
 #print(Primitive(s) mod q);
 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 L,i,n,d:
L:=[]:
n:=degree(P,x):
for d from 1 to n do
 if coeff(P,x,d) mod q<>0 then
  L:=[op(L), [coeff(P,x,d), d]]:
 fi:
od:
L:
end:

qMaxPer:=proc(q,d,x) local INI,pols,p,L,per,result,n:
INI:=[1,0$(d-1)]:
pols:=qPolsE(q,x,d):
n:=q^(d+1):
result:={}:
for p in pols do
 L:=qPolToList(q,p,x):
 #print(L);
 #print(SR(INI,L,n));
 #print(qFindPer(qSR(q,INI,L,n)));
 per:=FindPer(qSR(q,INI,L,n)):
 if per=q^d - 1 then
  result:=result union {p}:
 fi:
od:
result:
end:

qWisW2:=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
 #print(s);
 #print(Primitive(s) mod q);
 if irreduc(s) mod q and not Primitive(s) mod q then
  Si:=Si union {s}:
 elif not irreduc(s) mod q and Primitive(s) mod q then
  Sp:=Sp union {s}:
 elif irreduc(s) mod q and Primitive(s) mod q then
  Sip:=Sip union {s}:
 else
  Sne:=Sne union {s}:
 fi:
od:
[Sne,Si,Sp,Sip]:
end:

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

#It seems like they are not equal but it is off by the coefficients. But I may also be wrong.


#=====================================#
#3. Read and understand the wikipedia article on the DES
#Done