The verification procedure works by the following argument. There are several other variants (see K. Nyberg and R. A. Rueppel, Message recovery for signature schemes based on the discrete logarithm problem, Designs, Codes and Cryptography, 7:61–81, 1996). Prove that $\prod_{i