# Okay to post homework
# Ryan Badi, April 21, 2024, Homework 25

VerifyOpt1 := proc(n, G, B1, B2) local Gnew:
  Gnew := {}:
  for u in op(B1) do:
    for v in op(B1) do:
      if B2[{u, v}] = 1 then:
        Gnew := Gnew union {u, v}:
      fi:
    od:
  od:
  return evalb(G = Gnew):
end:

ZKP1 := 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:
    return VerifyOpt1(n, G, B1, B2):
  else:
    return evalb({seq(B2[{sig[pi[i]], sig[pi[i + 1]]}], i=1..n-1), B2[{sig[pi[n]], sig[pi[1]]}]} = {1}):
  fi:
end:

ZKP := proc(n, G, pi, K) local i:
  for i from 1 to K do:
    if not ZKP1(n, G, pi, ra(1)() + 1) then: return false: fi:
  od:
  return true:
end: