8.17. Considering the four examples from Problem 8.13, we see that the Elgamalscheme is nondeterministic: A given plaintext x has many valid ciphertexts, e.g., both x = 33 and x = 248 have the same ciphertext in the problem above.

1. Why is the Elgamal signature scheme nondeterministic?

2. How many valid ciphertexts exist for each message x (general expression)? How many are there for the system in Problem 8.13 (numerical answer)?

3. Is the RSA cryptosystem nondeterministic once the public key has been chosen?"