# Why is ElGamal considered non-deterministic?

One difference between RSA and ElGamal is that ElGamal isn't necessarily deterministic (while RSA is).

What makes it non-deterministic? Is this advantageous to security? How else does this property affect ElGamal encryption or the ElGamal signature scheme?

-
For public key encryption, this randomization of the encrypted message is important. If the public key encryption algorithm was not nondetermistic (that is, the encrypted message depended only on the plaintext message and the public key), then someone with an encrypted message $M$ and the public key $PK$ and a candidate plaintext message $P$ could test if the decryption of $M$ was $P$ (simply by encrypting $P$ using the public key $PK$, and checking if the result was $M$).