I am currently trying to make an implementation of the ElGamal encryption for educational purposes. As I understand it, when using the encryption with multiplicative cyclic groups, one generates a cyclic group for a safe private key as follows:
Find a safe prime number $p$ (of the form $p = 2*q + 1$ where $q$ is prime)
Find the generator of a cyclic group with order $q$ and modulo $p$ (i.e. a number $g$ less than $p$ such that $g^q \mod p = 1$ and $g^2 \mod p \neq 1$)
For example, for $p = 11$, we'd have $q = 5$, $g = 3, 4, 5$ or $9$, and the cyclic group would have the elements {$1, 3, 9, 5, 4$}.
Then, during the encryption stage, the one performing the encryption should convert $m$, the number representation of the message, into $m_1$, a member of this group. How is this done if $m$ doesn't belong to our group (for example, if it is $2, 6, 7, 8$ or $10$)?
If I am missing something, please tell me what did I get wrong!