Cryptography: how to determine if an element is in a finite field? 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?
 A: The multiplicative group $\mathbb F_p^\times$ is cyclic of order $p-1=2q$.
The group $\langle h\rangle$ is a subgroup thereof, hence of order $\in\{1, 2, q, 2q\}$. Then the order of $\langle g\rangle$ is $\in\{1,q\}$, an dI guess you would have started afresh in the first case. ;)
The only way for $m$ not to be in $\langle g\rangle$ is that $\langle m\rangle =\mathbb F_p^\times$. This is equivalent to $m^q\not\equiv 1\pmod p$.
A: For the particular case of the order $q$ subgroup $G$ of the multiplicative group $\mathbb F^{\times}_p$ modulo a safe prime $p = 2q+1$, there's a convenient trick: instead of working directly with the elements $a \in G$, we can work with the cosets $[a] = \{a,\,p-a\} = aH$, where $H = \mathbb F^{\times}_p/G = \{1,\,p-1\}$ is the order $2$ subgroup of $\mathbb F^{\times}_p$.
The trick is that we can represent the cosets by any of their members: if $a' \in [a]$ and $b' \in [b]$, we have $[a'b'] = [ab]$.  Thus, we can choose an arbitrary element of each coset to represent it; a convenient choice is to always take the smallest positive one.
This choice maps $G$ one-to-one to the range $1$ to $q$ — and, conveniently, the map is also onto, so we know that any number in this range is a representative of the coset $[a]$ for some $a \in G$, and that all the cosets thus obtained are distinct.
So we can just work with numbers from $1$ to $q$ instead of the actual elements of $G$, always remembering to reduce the results of calculations modulo $p$ and take the smaller element of the coset $[x] = \{x,\,p-x\}$.  Of course, actually figuring out which of $x$ and $p-x$ actually belongs in $G$ takes a bit more work, but fortunately, that's not actually something you need to do very often (if ever).
