Mapping between subgroups and the integers This question is a companion to the equivalent question on elliptic curves.
Preliminaries
Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime $p$. However, for security reasons, we do not use all the integers in $\mathbb{Z}^*_p$ but only a subset of them. The subset is of size $q&lt;p$ and $q$ is also a prime number. The subset is also chosen so that it also forms a group, $\mathbb{G}_q$, with closure under multiplication (a multiplicative subgroup). Number theory tells us that such a group can be found iff $q$ divides $(p-1)$.
With Elgamal in particular, messages must be encoded into $\mathbb{G}_q$. If the message is an $\ell$-bit bitstring $\{0,1\}^\ell$ and $\ell&lt;|q|$, then it can be treated like an integer and will be in $\mathbb{Z}_p$ (and $\mathbb{Z}_q$) (we'll ignore the corner case of all zeros). The problem is that it is unlikely to also be in $\mathbb{G}_q$ (depending on how much smaller $q$ is than $p$).
Questions
How can you map numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:

$p=2q+1$
$p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160

(I'll accept the best answer for the second case)
(As the second case appears not to be possible—see my answer—I've accepted an answer for the first case)
Format
This question is somewhat rhetorical for me personally, but I think it is a good place to gather different answers in one place (and things have been slow). With that in mind, use one technique per answer. Also relevant could be encoding-free Elgamal (such as hashed Elgamal) that sidesteps the problem.
For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$:


Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$.
If $x$ is a non-zero quadratic residue ($x = y^2 \mod p$ for some value $y$) then $x^q = y^{2q} = y^{p-1} = 1 \mod p$. Thus, every non-zero quadratic residue is a $q$-th root of $1$, therefore an element of $\mathbb{G}_q$.
Since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$. This implies that if $x$ is a quadratic residue, then $-x$ is not, and vice versa. Thus, there are $(p-1)/2 = q$ non-zero quadratic residues.


This yields the following mapping:


If $x \in \mathbb{G}_q$ then it is a square and has two square roots, $y$ and $-y$ for a value $y$. Computing the square root modulo $p$ is easy: $y = x^{(p+1)/4} \mod p$. $y$ can be viewed as an integer between $1$ and $p-1$. Set $z = y - 1$ if $y \leq q$, or $z = p - y - 1$ otherwise. This always yields a value such that $0 \leq z \lt q$, i.e. a value in $\mathbb{Z}_q$.
For the inverse mapping, just compute $(z+1)^2 \mod p$.