# Okay to post homework
# Ryan Badi, March 24, 2024, Homework 17

Help := proc(): print("qSR(q,INI,L,n), determine_period_length(qsr)"): 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:
  return M:
end:

determine_period_length := proc(qsr) local count, fail_count:
  fail_count := nops(qsr):
  count := 1:
  while qsr[1..count] <> qsr[count+1..2*count] do:
    count := count + 1:
	if count > fail_count then: return FAIL: fi:
  od:
  return count:
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:

#qPols(q, x, d): The SET of all polynomials of degree <=d in x mod q such that the constant term is not 0
qPols := proc(q, x, d) local S, s, i:
  option remember:
  if d = 0 then return {seq(i,i=1..q-1)}: fi:
  S := qPols(q, x, d - 1):
  return S union {seq(seq(s + i * x^d, i=1..q-1), s in S)}:
end:

#PolsE(x, d): The set of polynomials of EXACTLY degree d
PolsE := proc(x, d) local S, s:
  S := Pols(x, d - 1):
  return {seq(s + x^d, s in S)}:
end:

#qPolsE(q, x, d): The set of polynomials of EXACTLY degree d
qPolsE := proc(q, x, d) local S, s, i:
  S := qPols(2, x, d - 1):
  return {seq(seq(s + i * x^d, i = 1..q-1), s in S)}:
end:

#IsIr(P): Is P irreducible mod 2?
IsIr:=proc(P)
option remember:
evalb(Factor(P) mod 2=P mod 2):
end:

#qIsIr(q, P): Is P irreducible mod q?
qIsIr := proc(q, P)
  option remember:
  evalb(Factor(P) mod q = P mod q):
end:

#IsPr(P,x): is the polynomial P in x of degree d, say, primitive?
IsPr:=proc(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 2=1 then
     RETURN(false):
   fi:
od:
if rem(x^m,P,x) mod 2<>1 then
   print(`Something bad happened, Cocks' aritcle is wrong!, or more likely (according to George)`):
   print(`we messed up`):
    RETURN(FAIL):
fi:
true: 
end:

#qIsPr(q, P, x): is the polynomial P in x of degree d, say, primitive?
qIsPr := proc(q, P, x) local d, m, i:
  option remember:
  d := degree(P, x):
  m := q^d - 1:
 
  for i from 1 to m - 1 do:
    if rem((x^i)-1, P, x) mod q = 1 then:
      return false:
    fi:
  od:
  if rem(x^m, P, x) mod q <> 1 then:
     return FAIL:
  fi:
  return true: 
end:

#WisW(d,x): inputs a pos. integer d and outputs the list of sets
#of pol. of degree exactly d such that
#(i) neither (ii) Irred. but not Primitive (iii) Primitive but not irreducible (iv) both
WisW:=proc(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:=PolsE(x,d):
Si:={}: Sp:={}: Sip:={}: Sne:={}:

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

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

#qWisW(q,d,x): inputs a pos. integer d and outputs the list of sets
#of pol. of degree exactly d such that
#(i) neither (ii) Irred. but not Primitive (iii) Primitive but not irreducible (iv) both
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: