# 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:

1. Find a safe prime number $p$ (of the form $p = 2*q + 1$ where $q$ is prime)

2. 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!

• It seems my understanding of ElGamal key generation was broken; we do not have to use a group of order $q$, rather, we should use a group of order $p$, where the problem does not exist Commented Jan 24, 2015 at 20:03
• Your asking about how to encode arbitrary integers to elements of cyclic subgroup $\mathbb G_q$. This question has been covered here Commented Jan 24, 2015 at 22:26

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$
• Mints97: Yes of course, it's one of the possible alternative, I've understand your problematic. But we can do better. If you have the liberty of choosing the prime modulus p. Select it such as $p \equiv 1 \; mod \;4$, this condition is equivalent to $(-1) \in QR(p)$. Then randomly select $a \in F_p$ imply $a \in QNR(p) \; \Leftrightarrow -a \in QR(p)$. Commented Jan 24, 2015 at 23:03
• Sorry for the typo! You must understand above $p \equiv 3 \; mod \; 4$ and $-1 \in QNR(p)$ Commented Jan 24, 2015 at 23:15