Example for Cyclic Groups and Selecting a generator

In Cryptography, I find it commonly mentioned:

Let G be cyclic group of Prime order q and with a generator g.

Can you please exemplify this with a trivial example please! Thanks.

-

4 Answers

A better example (because the log problem is hard, which is not the case for the additive groups): the multiplicative group of $\mathbb{Z}_{p} = \{ 1,2,\ldots,p-1\}$ under multiplication. Say for $p=11$, we have $G = \{1,2,\ldots,10\}$, and not all elements are generators, e.g. $1$ is not. Let's try 2: $$2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16 = 5, 2^5 = 10 = -1,$$ $$2^6 = -2 = 9, 2^7 = -4 = 7, 2^8 = -8 = 3, 2^9 = 6, 2^{10} = 12 = 1$$ again. So 2 is a generator, and the discrete log for 3 equals 8, as $2^8 = 3 \mod 11$ etc. For large primes, this gets harder and harder (we cannot make a table like this anymore). In general, you need to work a bit to find a generator, but they always exist. E.g. see the wikipedia page on this, e.g if we choose $p = 2q+1$, where $q$ is also prime (a "safe prime" in cryptography) then $g$ is a multiplicative primitive in $\mathbb{Z}_p$ iff $g^{\frac{p-1}{2}} = -1 \mod p$, and this is easy to test (fast modular exponentiation algorithms exist). As there are $\phi(\phi(n)) = \phi(2q) = q-1$ many primitive elements, a picking a few random numbers and testing them will give a primitive element. In practice, a set of fixed primes, and corresponding generators, have already been fixed by a committee, like in the TLS/SSL standard, so that a user need not generate them himself, but can just say "use group x from that standard"; but like I said, it's not that hard for a PC to find primitive elements.

-
Nice. Correctly when I was thinking about it. :) Thanks, but "work a bit" meaning its by brute force. Or some specific method <a href=" en.wikipedia.org/wiki/…; for finding the primitive root </a> There is a table given, Do we have to refer this whenever we are required to choose a generator? – bala maverick Feb 26 '11 at 11:29
For larger primes it gets even more difficult. In that wiki link for primitive roots, for finding primitive roots, we need to check every candidate. Wont cryptographic schemes become inefficient while choosing a generator this way? @yunone – bala maverick Feb 26 '11 at 11:48
Exactly what i was looking for. It is an interesting fact that primes and generators are being maintained before hand and not computed on the fly. – bala maverick Feb 28 '11 at 3:34
Just wanted to add that the national logarithm problem is "difficult" to solve, but not NP-hard. Needed to mention this to sleep well. – Sebastian Hojas Nov 8 '15 at 17:00

In fact if you take the group $(\mathbb{Z}_{p},+)$ for a prime number $p$, then every element is a generator.

• Take $G= \{a^{q}=e, a ,a^{2}, \cdots, a^{q-1}\}$. Now $|G|=q$ and $G = <a>$, which means that $G$ is generated by $a$.
-
@Chandru1 Thanks. But is it true that every element in a prime order group is a generator of Zp? And here is Zp a group of integer elements modulo p? – bala maverick Feb 26 '11 at 10:38
@bala: Yes, in group or prime order you have every element to be a generator. – anonymous Feb 26 '11 at 10:41
@Chandru1 The above comment by Yunone says that only numbers relatively prime to the modulus are generators but you say all the elements are generators. Am i missing anything here? – bala maverick Feb 26 '11 at 10:57
@bala: but for $n=p$ all the numbers $p-1, p-2, \cdots$ are relatively prime to $p$ right? – anonymous Feb 26 '11 at 11:02
@Chandru1 :) Oops. I am starting to feel dumb! Thanks for the effort. I am getting it now. :) – bala maverick Feb 26 '11 at 11:08

A common example would be the integers modulo $5$, $\mathbb{Z}_5$. This a cyclic group under addition with a possible generator $1$, and has prime order $5$.

-
Thanks for the effort. A small clarification. Is there any specific method of choosing a generator from such a group? In case if there is a method how long (time) would it take to choose one? – bala maverick Feb 26 '11 at 10:30
@bala maverick, at least for the integers modulo so $m$, any integer relatively prime to the modulus will be a generator. $1$ is always a simple go to generator, since any positive integer is a sum of $1$s. It is helpful to note that every finite cyclic group is isomorphic to the group $\{ [0], [1], [2], \dots, [n − 1] \}$ of integers modulo $n$ under addition, and any infinite cyclic group is isomorphic to $\mathbb{Z}$ under addition, as taken from wikipedia. – yunone Feb 26 '11 at 10:40
Almost there. But how do we select generators from multiplicative groups of prime order? Here thanks to you, addition was easy to understand. – bala maverick Feb 26 '11 at 11:16

A cyclic group has one or more than one generators. For example: Z = {1,-1,i,-i} is a cyclic group of order 4. Where the generators of Z are i and -i.

-