#OK TO POST
#NURAY KUTLU HW 14

Encode113G:=proc(x,q) local p, x1,x2,x3,x4,y1,y2,y3,y4,i,S:
 p:= nops(x):
 y1 := add(x[i], i=1..p) mod q+ x1 + x2 + x3 + x4 = 0:
 y2 := add(i * x[i], i=1..p) mod q+ (p+1 mod q )*x1+ (p+2 mod q)*x2 + (p+3 mod q)*x3 + (p+4 mod q)*x4 =0:
 y3 := add(i^2 * x[i], i=1..p) mod q + ((p+1 mod q)^2 mod q)*x1 + ((p+2 mod q)^2 mod q)*x2 + ((p+3 mod q)^2 mod q)*x3 + ((p+4 mod q)^2 mod q)*x4 =0:
 y4 := add(i^3 * x[i], i=1..p) mod q+ ((p+1 mod q)^3 mod q )* x1 + ((p+2 mod q)^3 mod q)*x2 + ((p+3 mod q)^3 mod q)*x3 + ((p+4 mod q)^3 mod q)*x4 =0:
 S := msolve({y1,y2,y3,y4}, q):
 subs(S, [op(x), x1,x2,x3,x4]):
end:


Sy113G:=proc(x,q) local r,i:
[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:=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:

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:=[]:
for i1 from 0 to nops(y) 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: