6
$\begingroup$

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 4

7

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.

  • 0
    Just wanted to add that the national logarithm problem is "difficult" to solve, but not NP-hard. Needed to mention this to sleep well.2015-11-08
2

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

  • 0
    @bala: Good that you got it. Thanks for asking.2011-02-26
1

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$.

  • 0
    Almost there. But how do we select generators from multiplicative groups of prime order? Here thanks to you, addition was easy to understand.2011-02-26
1

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.