I'm working on a cryptography project that is basically a semantically secure modification to ElGamal. My question is: how do I determine if an element is in a finite field without calculating the whole field?
If we have two primes, a $q=5$ and a $p=11$ ($p = 2q + 1$, a safe prime). I can pick a $g$ by doing $g = h^2 \bmod p$. Let's say I use $h=6$ and end up with $g=3$. $g$ then generates its own group $\left<g\right>$. For semantic security, the message $m$ that I am going to encrypt must be in $\left<g\right>$... otherwise I must encrypt the additive inverse of $m$ which is guaranteed to be in $\left<g\right>$.
My question then is: if I have $m=5$, how do I determine whether that is in $\left<g\right>$ without calculating the whole field?
Obviously it would be really easy to calculate the field for the values in my example, but I'm using 1024-bit primes and generating the field isn't going to happen in my lifetime. Any suggestions?