#1: Reading

#2: 

VerifyOpt1:=proc(n, G, B1, B2) local:

#given G and B1 (vert perm), B2 (edge perm)

#encode the edges of G using B1 and check if equiv to B2

#B1, B2 both tables

#G is a set of edges. Build new set H encoded edges
#build table of encoded edges and ask if equal to B2

#transform edges

H:={}

for e in G do

H:=H union {B1[e[1]], B1[e[2]]}:

od:

#build new table

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


EqualEntries(H2, B2);

end:


#___

ZKP1 := proc(n,G,pi,Opt) local B1,B2,i,j,sigma:
# B1 maps vertices to vertices according to a new permutation (sigma)
# B2 is a table whose output is 0 or 1 if edge exists or not (maps edges to 0 or 1)

sigma := randperm(n): # come up with a NEW random permutation of vertices

# build B1: map vertices under the permutation sigma
for i from 1 to n do 
    B1[i] := sigma[i]: 
od:

# build B2: check if each edge is in G or not, add 0 or 1 to table
for i from 1 to n do
    for j from i+1 to n do
        if member({i,j},G) then 
            B2[{sigma[i],sigma[j]}] := 1:
        else
            B2[{sigma[i],sigma[j]}] := 0:
        fi:
    od:
od:

if Opt = 1 then 
    return(VerifyOpt1(n,G,B1,B2));
else  
	if { seq( B2[ { sigma[pi[i]], sigma[pi[i+1]] } ], i=1..n-1 ), B2[ {sigma[pi[n]], sigma[pi[1]]} ] }={1} return (TRUE);
	else return(FALSE);
       fi:
fi:
end:

#3 


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

ZKP:=(n,G,pi,K) local k, OPTk, listZKP1, x, settt:
k:=0
listZKP1:=[]:
while k<=K do

if LD(1/2)=true then OPTk:=1
else OPTk:=2
fi:
x:=ZKP1(n,G,pi,OPTk);
listZKP1:=[op(listZKP1), x]:
k:=k+1
od:

settt:=listtoset(listZKP1);
if settt={true}:
return(TRUE):
else:
return(FAIL)
fi:


end:



#----------------------------------------



# C25.txt, 04/18/2024

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

with(combinat): # needed to produce random permutation in RHG


# inputs a positive rational number from 0 to 1 
# outputs "true" with probability p 
# picks a random number from 1 to the denominator of input p 
# compare to numerator of input p, return true if less than numer(p)
LD := proc(p) local i:
i := rand(1..denom(p))():
if i <= numer(p) then   # could also just return (i <= p)
    true:
else
    false:
fi:
end:

## sample calls
# LD(1/2);
## check distribution
# add(x[LD(1/2)],i=1..1000); # close to 50/50 !




# inputs a positive integer n, outputs a (simple) graph on n vertices
# the probability of an edge is p (independently of each other)
RG := proc(n,p) local G,i,j:

G :={}: # initialize set of edges

# decide if edge {i,j} is in the graph
for i from 1 to n do
    for j from i+1 to n do  # no loops, so check for j > i. can't have i=j
        if LD(p) then   # recall LD returns boolean true/false
            G := G union {{i,j}}: # add edge to graph
        fi:
    od:
od:

G: # don't forget to return the graph!
end:

## sample calls -- note that the edge set is returned
# RG(10, 1/2);
# RG(10, 1/10);

# nops(%); # expect roughly p * (n choose 2)


# COPY PASTED FROM RG() WITH MODIFICATIONS
# inputs a positive integer n, outputs a (simple) HAMILTONIAN graph on n vertices
# the probability of an edge is p (independently of each other) 
# TOGETHER WITH THE HAMILTONIAN PATH
# THE OUTPUT IF [G,permutation] WHERE THE PERMUTATION OF {1,...,n}
# IS THE (SECRET) HAMILTONIAN CYCLE. WE RETURN IT TO CHECK SUCCESS LATER

RHG := proc(n,p) local G,i,j,pi:
pi := randperm(n): # from combinat package, produces random permutation of [n]

# initialize set of edges, this time including the cycle of edges from pi
# don't forget to close the cycle with the edge {pi[n],pi[1]}
G := {seq( {pi[i],pi[i+1]}, i=1..n-1 ), {pi[n],pi[1]}}:

# decide if edge {i,j} is in the graph
for i from 1 to n do
    for j from i+1 to n do  # no loops, so check for j > i. can't have i=j
        if LD(p) then   # recall LD returns boolean true/false
            G := G union {{i,j}}: # add edge to graph
            # MIGHT DUPLICATE WITH HAM. CYCLE EDGES, BUT UNION KEEPS US SAFE
        fi:
    od:
od:

[G,pi]: # return graph and permutation this time 
end:

## sample calls
# RHG(10,1/10);
# RHG(100,1/2); # very dense, print at your own peril
## if very dense, hard to find the ham path, of course. this will be useful later


# one round of blum's protocol pg. 3-4 of zero knowledge proof (ZKP) article
# inputs a graph G on n vertices, a Ham cycle pi, and Opt = 1 or Opt = 2 (described in article)
# Opt1: show all n + binomial(n,2) boxes
# Opt2: show the contents of the n boxes corresponding to the mapping of Ham cycle

ZKP1 := proc(n,G,pi,Opt) local B1,B2,i,j,sigma:
# B1 maps vertices to vertices according to a new permutation (sigma)
# B2 is a table whose output is 0 or 1 if edge exists or not (maps edges to 0 or 1)

sigma := randperm(n): # come up with a NEW random permutation of vertices

# build B1: map vertices under the permutation sigma
for i from 1 to n do 
    B1[i] := sigma[i]: 
od:

# build B2: check if each edge is in G or not, add 0 or 1 to table
for i from 1 to n do
    for j from i+1 to n do
        if member({i,j},G) then 
            B2[{sigma[i],sigma[j]}] := 1:
        else
            B2[{sigma[i],sigma[j]}] := 0:
        fi:
    od:
od:

if Opt = 1 then 
    [op(B1), op(B2)]: # remember that tables must be returned with "op" because maple is weird
else    # assumes the user is smart enough to only enter 1 or 2 for Opt
    # set of where the edges of Ham cycle were mapped to
    # the last pair is the cycle wrapping around n to 1 again
    { seq( B2[ { sigma[pi[i]], sigma[pi[i+1]] } ], i=1..n-1 ), B2[ {sigma[pi[n]], sigma[pi[1]]} ] }: 
fi:
end:


## sample function calls
# H := RHG(5,1/2): # recall that the output is H = [graph, permutation]
# ZKP1(5,op(H),1): # need op(H) instead so that maple can read the arguments properly

# J := RHG(5,1/2);
# G := J[1]:
# pi := J[2]:
# ZKP1(5,G,pi,1);
# ZKP1(5,G,pi,2); # should return {1}. aurora thinks this is because the permutation is reversed?

## homework will be to continue working on this, something about option 2 needing a macro