#OK to post homework
#Joseph Koutsoutis, 03-10-2024, Assignment 14

read `C14.txt`:
with(NumberTheory):

#1 

Encode113G := proc(x,q) local n,a,b,c,d,eq1,eq2,eq3,eq4,i,S:
 n := nops(x) + 4:
 eq1 := 0 = add(x[i], i=1..nops(x)) + a + b + c + d:
 eq2 := 0 = add(i * x[i], i=1..nops(x)) + (n-3)*a + (n-2)*b + (n-1)*c + (n)*d:
 eq3 := 0 = add(i^2 * x[i], i=1..nops(x)) + (n-3)^2*a + (n-2)^2*b + (n-1)^2*c + (n)^2*d:
 eq4 := 0 = add(i^3 * x[i], i=1..nops(x)) + (n-3)^3*a + (n-2)^3*b + (n-1)^3*c + (n)^3*d:
 S := msolve({eq1,eq2,eq3,eq4}, q):
 subs(S, [op(x), a,b,c,d]):
end:


RV113G:=proc(n,q): Encode113G(RV(q,n-4),q):end:


Sy113G := proc(x,q) local i,r:
 [seq(add(x[i] * i^(r-1), i=1..nops(x)) mod q, r=1..4)]:
end:


Decode113G := proc(y,q) local S,eq,i,L,i1,j1,a,b,P,Q,R:
 S := Sy113G(y,q):
 if S = [0$4] then
  return(y):
 fi:

 eq := (S[2]^2-S[1]*S[3])*i^2+(S[1]*S[4]-S[2]*S[3])*i+ (S[3]^2-S[2]*S[4]) mod q:
 P := coeff(eq, i, 2):
 Q := coeff(eq, i, 1):
 R := coeff(eq, i, 0):

 if eq = 0 then
  i := S[2]/S[1] mod q:
  a := S[1]:
   return(y-[0$(i-1),a,0$(nops(y)-i)] mod q):
 fi:

 if P <> 0 and R <> 0 then:
  # Instead of finding the roots by plugging in all values of q, I use the
  # ModularSquareRoot function and catch the error if there is no square root.
  try:
   i1 := (-Q + ModularSquareRoot(Q^2 - 4*P*R, q))/(2*P) mod q:
   j1 := (-Q - ModularSquareRoot(Q^2 - 4*P*R, q))/(2*P) mod q:
   b := (i1*S[1] - S[2]) / (i1-j1):
   a := S[1] - b:
   return(y - [0$(i1-1),a,0$(nops(y)-i1)] - [0$(j1-1),b,0$(nops(y)-j1)] mod q):
  catch:
  end try:
 fi:
 
 return(FAIL): 
end:

#2 done