Converting a number to a member of a multiplicative cyclic group 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!
Use the Legendre symbol in your case.
Explanation: when $p=2.q+1$, the order of the multiplicative group of $F_p$ is p-1=2q.
Then there is no other alternative, when you select a random number, it could be a quadratic Residue with probability $\frac{1}{2}$.
The legendre symbol of any number a, is : $a^{\frac{p-1}{2}}=a^{q}=\pm 1$

Then except the number 1, all the other quadratic residue (Legendre symbol is 1) have order q.