Retrieving correct ciphertext from additive ElGamal I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$. 

From what I've read, the result of such computations is a function of $k$ e.g. for $g=3, M=4, \pmod{17}$ we have $3^4=13 \pmod{17}$ but computing the discrete log however gives $M=4 + 16k$. How do I know that $M=4$ and not $M=20$? 

Note that for $g=3,M=20 \pmod{17}$ we also get $M=4+16k$.
The answer is simple if you know the answer to this question:


  
  Can you use 20 instead of 4 for a plaintext?
  



If you can they will be the same encryption and no problem since 20 and 4 same for yo.
If you cannot, therefore, you cannot decide the plaintext after you decrypted. 


To solve this issue you have to limit your message space into $\pmod{17}$ and divide your longer message block in an appropriate way. Now, you know, you have to take the smallest positive value where $k=0$.

The problem with adding homomorphically is a different issue. Before the computation, you have to consider the upper bound of your calculations and choose your modulus according to it. For example, if you are going to add 4 and 8 there is no problem, however, if you are going to add 10 and 9 you have to consider a bigger modulus.