Help16:=proc(): print(` From Nuray Kutlu: Encode113G(x,q), Sy113G(x,q), Decode113G(y) `):
print(` From Joseph  Koutsoutis: EncodeBCH(x,d,q)  (n := nops(x) + d - 1),  DecodeBCH(x,d,q)`):
end:

#start C14.txt, March 4, 2024
Help14:=proc(): print(` RV(q,n), Encode113(x) , RV113(), Sy113(x) ,Decode113(y) `):end:
#Code by Joseph Koutsoutis

#RV(q,n): A random word of length n in {0,1,..,q-1}
RV:=proc(q,n) local ra,i:
ra:=rand(0..q-1):
[seq( ra(), i=1..n)]:
end:

Encode113 := proc(x) local a,b,c,d,eq1,eq2,eq3,eq4,i,S:
 eq1 := 0 = add(x[i], i=1..6) + a + b + c + d:
 eq2 := 0 = add(i * x[i], i=1..6) + 7*a + 8*b + 9*c + 10*d:
 eq3 := 0 = add(i^2 * x[i], i=1..6) + 7^2*a + 8^2*b + 9^2*c + 10^2*d:
 eq4 := 0 = add(i^3 * x[i], i=1..6) + 7^3*a + 8^3*b + 9^3*c + 10^3*d:
 S := msolve({eq1,eq2,eq3,eq4}, 11):
 subs(S, [op(x), a,b,c,d]):
end:
#End Code by Joseph Koutsoutis

#RV113(): a random member of the Ex. 11.3 code
RV113:=proc(): Encode113(RV(11,6)):end:

#Sy113(x): The vector of length 4 that is the syndrom of the received vector x
Sy113:=proc(x) local i,r:
[seq(add(x[i]*i^(r-1),i=1..nops(x)) mod 11,r=1..4)]:
end:

#Decode113(y): if the reveived vector was y, assuming at most two errors,
#outputs the intended code word
Decode113:=proc(y) 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 11:

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


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

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

#March 7, 2024 C15.txt
Help15:=proc(): print(`S(x,y), aS(a), OurPF(R,t),  aSr(a) , `):end:

#S(x,y): maps a pair of lists of numbers of the same length, n, say,
#and outputs a list of numbers of length 2*n
#[x[1]+....+x[n],x[1]*y[1]+...+x[n]*y[n],...., x[1]*y[1]^(2*n-1)+.. x[n]*y[n]^(2*n-1)]
S:=proc(x,y) local n,i,r:
if not (type(x,list) and type(y,list) and nops(x)=nops(y)) then
 RETURN(FAIL):
fi:
n:=nops(x):
[ seq(add(x[i]*y[i]^r,i=1..n),r=0..2*n-1)]:
end:

#aS(s): reverse S(x,y) using Maple's solve command.
#inputs a list of length 2*n and outputs lists x,y of
#length n, such that S(x,y)=a
aS:=proc(a) local n,x,y,X,Y,i,eq,var,r:
if not( type(a,list) and nops(a) mod 2=0) then
 RETURN(FAIL):
fi:
n:=nops(a)/2:
eq:={seq(add(x[i]*y[i]^r,i=1..n)=a[r+1],r=0..2*n-1)}:
var:={seq(x[i],i=1..n),seq(y[i],i=1..n)}:
var:=solve(eq,var)[1]:
[[seq(subs(var,x[i]),i=1..n)],[seq(subs(var,y[i]),i=1..n)]]:
end:


#corrected after class
#OurPF(R,t): inputs a rational function of t outputs the
#partial fraction decomopition over the complex numbers of the form
#[a1,r1],..., [an,rn] where 1/r1,..., 1/rn are the complex roots of the
#bottom
OurPF:=proc(R,t) local n,Top,Bot,zer,Y,i:
Top:=numer(R):
Bot:=denom(R):
zer:=[solve(Bot,t)]:
n:=nops(zer):
Y:=sort([seq(1/zer[i],i=1..nops(zer))]):
[[seq(-Y[i]*subs(t=1/Y[i],Top)/subs(t=1/Y[i],diff(Bot,t)),i=1..n)],Y]:
end:


#aSr(a): solves the system of Ramanujan using his method with partial fractions
#outputs the rational function whose partial fraction would solve the system
#modified after class
aSr:=proc(a) local n,A,B,i,Top,Bot,f,eq,var,t:
if not( type(a,list) and nops(a) mod 2=0) then
 RETURN(FAIL):
fi:
n:=nops(a)/2:

Top:=add(A[i+1]*t^i,i=0..n-1):

Bot:=1+add(B[i]*t^i,i=1..n):

#Top/Bot=add(a[i]*t^(i-1),i=1..2*n):

f:=expand(Top-Bot*add(a[i]*t^(i-1),i=1..2*n)):
eq:={seq(coeff(f,t,i),i=0..2*n-1)}:
var:={seq(A[i],i=1..n),seq(B[i],i=1..n)}:
var:=solve(eq,var):
OurPF(normal(subs(var,Top)/subs(var,Bot)),t):
end:


###new code from students

#Code by 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:
#end code from NURAY KUTLU








#Start code from Joseph Koutsoutis, 03-10-2024, Assignment 15

read `C15.txt`:
with(LinearAlgebra):

OurPF:=proc(R,t) local n,Top,Bot,zer,Y,i:
Top:=numer(R):
Bot:=denom(R):
zer:=[solve(Bot,t)]:
n:=nops(zer):
Y:=sort([seq(1/zer[i],i=1..nops(zer))], (a,b) -> evalf(a) < evalf(b)): # I changed this line
[[seq(-Y[i]*subs(t=1/Y[i],Top)/subs(t=1/Y[i],diff(Bot,t)),i=1..n)],Y]:
end:

# since Maple appears to sort expressions with radicals in an unexpected way.
# For example, sort([sqrt(5)/2-1/2,sqrt(5)/2+3/2]) outputs [sqrt(5)/2+3/2,sqrt(5)/2-1/2].


#3

qS := proc(x,y,q) local n,i,r:
if not (type(x,list) and type(y,list) and nops(x)=nops(y)) then
 RETURN(FAIL):
fi:
n:=nops(x):
[ seq(add(x[i]*y[i]^r,i=1..n) mod q,r=0..2*n-1)]:
end:


qOurPF:=proc(R,t,q) local n,Top,Bot,zer,Y,i:
Top:=numer(R):
Bot:=denom(R):
zer:=[msolve(Bot,q)]:
n:=nops(zer):
Y:=sort([seq(subs(zer[i], 1/t) mod q,i=1..nops(zer))]):
[[seq(-Y[i]*subs(t=1/Y[i],Top)/subs(t=1/Y[i],diff(Bot,t)) mod q,i=1..n)],Y]:
end:


qaSr:=proc(a,q) local n,A,B,i,Top,Bot,f,eq,var,t:
if not( type(a,list) and nops(a) mod 2=0) then
 RETURN(FAIL):
fi:
n:=nops(a)/2:

Top:=add(A[i+1]*t^i,i=0..n-1):

Bot:=1+add(B[i]*t^i,i=1..n):

f:=expand(Top-Bot*add(a[i]*t^(i-1),i=1..2*n)) mod q:
eq:={seq(coeff(f,t,i),i=0..2*n-1)}:
var:={seq(A[i],i=1..n),seq(B[i],i=1..n)}:
var:=msolve(eq,q):
qOurPF(normal(subs(var,Top)/subs(var,Bot)) mod q,t, q):
end:

#4

EncodeBCH := proc(x,d,q) local S,eqs,i,j,n,y:
 n := nops(x) + d - 1:
 eqs := {seq(add(i^j * x[i], i=1..nops(x)) + add(i^j * y[i], i=(nops(x)+1)..n), j=0..(d-2))}:
 S := msolve(eqs, q):
 subs(S, [op(x), seq(y[i], i=(nops(x)+1)..n)]):
end:



#5


UpperTriangular := proc(mat117,aug117,q) local t,curr_row,i,j,k,tmp,M,aug:
 M := mat117:
 aug := aug117:
 t := nops(M):
 curr_row := 1:
 for j from 1 to t do:
  for i from curr_row to t do:
   if M[i][j] <> 0 then:
    tmp := M[i]:
    M[i] := M[curr_row]:
    M[curr_row] := tmp:

    tmp := aug[i]:
    aug[i] := aug[curr_row]:
    aug[curr_row] := tmp:
    
    for k from curr_row+1 to t do:
     aug[k] := aug[k] - aug[curr_row] * M[k][j] / M[curr_row][j] mod q:
     M[k] := M[k] - M[curr_row] * M[k][j] / M[curr_row][j] mod q:
    od:
    curr_row += 1:
   fi:
  od:
 od:
 M,aug:
end:

DecodeBCH := proc(d,q,x) local t,a,i,j,r,n,e,matrix117,aug117,eqs117,A,B,locator,evaluator,theta,errs,X,Y:
 t := (d-1) / 2: 
 n := nops(x):
 a := [seq(add(i^r * x[i], i=1..n) mod q, r=0..(2*t-1))]:
 
 matrix117 := [seq([seq(a[t-i+j], i=1..t)], j=1..t)]:
 aug117 := [seq(-a[t+j] mod q, j=1..t)]:
 matrix117, aug117 := UpperTriangular(matrix117, aug117, q):
 e := Rank(matrix117):
 eqs117 := {seq(aug117[i] = add(matrix117[i][j] * B[j], j=1..e), i=1..e)}:
 
 locator := 1 + subs(msolve(eqs117, q), add(B[i] * theta^i, i=1..e)):

 for i from 1 to e do:
  A[i] := add(a[j] * coeff(locator, theta, i-j), j=1..i) mod q:
 od:
 evaluator := add(A[i] * theta^(i-1), i=1..e):
 errs := qOurPF(evaluator/locator, theta, q):

 X := errs[1]:
 Y := errs[2]:
 x + add(-[0$(Y[i]-1), X[i], 0$(n-Y[i])], i=1..nops(X)) mod q:
end: 

#End  code from Joseph Koutsoutis, 03-10-2024, Assignment 15