#Isaac Lam, March 17th 2024, HW14

Encode113G:=proc(x, q) local x1,x2,x3,x4,equations,i,j,S,n:
n:=nops(x);
equations:={seq(0=add(x[i],i=1..n)+((n+1)^j)*x1+((n+2)^j)x2b+((n+3)^j)*x3+((n+4)^j)*x4,j=0..3)};
S:=msolve(equations,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,j,L,i1,a,b:
S:=Sy113(y):
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:

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:

#L is the list of roots of eq (mod q)
L:=[]:
for i1 from 0 to q-1 do
if subs(i=i1,eq) mod q=0 then
L:=[op(L),i1]:
fi:
od:
i:=L[1]:
j:=L[2]:

b:=(i*S[1]-S[2])/(i-j) mod q:
a:=S[1]-b mod q:
y-[0$(i-1),a,0$(j-i-1),b,0$(nops(y)-j)] mod q:
end: