# 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 – Mints97 Jan 24 '15 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 – cygnusv Jan 24 '15 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)$. – Robert NACIRI Jan 24 '15 at 23:03
• Sorry for the typo! You must understand above $p \equiv 3 \; mod \; 4$ and $-1 \in QNR(p)$ – Robert NACIRI Jan 24 '15 at 23:15