#April 18, 2024, Zero Knowledge Proofs
Help:=proc(): print(`LD(p), RG(n,p), RHG(n,p), OneRound(n,G,pi,Opt)  `): end:

with(combinat):

LD:=proc(p) local i: i:=rand(1..denom(p))(): if i<=numer(p) then true: else false:  fi: end:

#RG(n,p): Random graph on vertices {1,...,n}, with prob. of an edge being p
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): Random Hamiltonian graph on vertices {1,...,n}, with prob. of an edge being p
#together with the Hamiltonian path
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:


#OneRound(n,G,pi,Opt): inputs a graph G with a Hamitonian cycle pi, if Opt=1  then reveal the isomorphic graph, and sig, if Opt=2 then reveal the
#image of the Hamiltonian path
OneRound:=proc(n,G,pi,Opt) local sig,i,j,B1,B2:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[pi[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([op(B1),op(B2)]):
else
 RETURN
({seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1), B2[{sig[pi[n]],sig[pi[1]]}]}):
fi:

end: