#Please do not post homework
#Lucy Martinez, 04-21-2024, Assignment 25


# Problem 2: Write a procedure VerifyOpt1(n,G,B1,B2)
# that inputs a positive integer n, a graph (set of edges) G, 
# and tables B1 (of size n) and B2 (of size binomial(n,2)) and
# outputs true if it is a faithful relabling of the graph G, otherwise false.

# Having done that Modify procedure ZKP1(n,G,pi,Opt) to return true or false, as follows:
# If it is Option 1, then it returns VerifyOpt1(n,G,B1,B2)
# If it is Option 2, then it returns true if you get {1}, otherwise returns false

#inv(pi): the inverse of the permutation pi
inv:=proc(pi) local T,i:
for i from 1 to nops(pi) do
T[pi[i]]:=i:
od:
[seq(T[i],i=1..nops(pi))]:
end:


VerifyOpt1:=proc(n,G,B1,B2) local i1,i,j,b2,G1,T,T1,T11,T2,T22:
G1:={}:
T:=[op(op(eval(B1)))]:
T1:=[seq(B1[i],i=1..nops(T))]:
T1:=convert(T1,list):
T11:=inv(T1):
T2:=[op(op(eval(B2)))]:
T22:=[seq([op(T2[i])],i=1..nops(T2))]:
for i1 from 1 to nops(T22) do
 b2:=[op(T22[i1][1])]:
 i:=b2[1]:
 j:=b2[2]:
 if T22[i1,2]=1 then
  G1:=G1 union {{T11[i],T11[j]}}:
 fi:
od:

if G=G1 then
 true:
else
 false:
fi:
end:




ZKP1:=proc(n,G,pi,Opt) local B1,B2,i,j,sig,T:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:

for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
    B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:


if Opt=1 then
 return VerifyOpt1(n,G,B1,B2):
else
 T:={seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:
 if T={1} then
  return true:
 else
  return false:
 fi:
fi:
end:


# Problem 3: Write a procedure ZKP(n,G,pi,K)
# that uses (the modified) ZKP1(n,G,pi,Opt) by having K rounds,
# and at each round, picking Option 1 or Option 2 each with probability 1/2
# and returning true if and only if ZKP1(m,G,pi,Opt) always returns true.
ZKP:=proc(n,G,pi,K) local i,val,ra,Opt,result:
result:={}:
for i from 1 to K do
 ra:=rand(0.0..1)():
 if ra<=1/2 then
  Opt:=1:
 else
  Opt:=2:
 fi:
 val:=ZKP1(n,G,pi,Opt):
 if val=true then
  result:=result union {true}:
 fi:
od:
if op(result)=true then
 true:
else
 false:
fi:
end:



###################################C25.txt

Help25:=proc(): 
 print(`LD(p), RG(n,p), RHG(n,p), ZKP1(n,G,pi,Opt)`):
end:

with(combinat):


#LD(p): inputs a pos. rational number from 0 to 1 and  outputs true with prob. p
LD:=proc(p) local i:
i:=rand(1..denom(p))(): 

if i<=numer(p) then
 true:
else
 false:
fi:
end:



#RG(n,p): inputs a pos. integer n and outputs a simple graph on n vertices
# where the prob of an edge is p (independently)
RG:=proc(n,p) local i,j,G:
G:={}:
for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
G:  
end:



#RHG(n,p): inputs a pos. integer n and outputs a simple HAMILTONIAN graph
# on n vertices where the prob of an edge is p (independetly)
# together with the Hamiltonian path
# The output is a pair [G,permutation] where the permutation of {1,...,n}
# is the Hamiltonian cycle that you know and you don't want anyone else to know
# BUT you do want to convince them that you DO know
RHG:=proc(n,p) local i,j,G,pi:
pi:=randperm(n):
G:={seq({pi[i],pi[i+1]},i=1..n-1), {pi[n],pi[1]}}:

for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
[G, pi]:  
end:


#ZKP11(n,G,pi,Opt): Does ONE ROUND of the Blum protocol.
# Inputs a graph n, G, a Hamiltonian pi, and Opt=1 or 2 
# Opt=1: you show all the n+binomial(n,2) boxes
# Opt=2: you show the contents of the n boxes correponsing to the mapping of
#  your Hamiltonian
#ZKP1(n,G,pi,Opt): Does ONE ROUND of the Blum protocol. Inputs a graph n,G,
#a Hamiltonian pi, and Opt=1 or 2 Opt=1 you show all the n+binomial(n,2) boxes
#Opt2, you show the contents of the n boxes correponsing to the mapping of
#your Hamiltonian
ZKP11:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:

for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:

if Opt=1 then
 [op(B1),op(B2)]:
else
 {seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:
fi:
end: