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
    Nice. Correctly when I was thinking about it. :) Thanks, but "work a bit" meaning its by brute force. Or some specific method for finding the primitive root There is a table given, Do we have to refer this whenever we are required to choose a generator?2011-02-26
  • 0
    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? @yunone2011-02-26
  • 0
    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.2011-02-28
  • 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
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
    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?2011-02-26
  • 0
    @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](http://en.wikipedia.org/wiki/Cyclic_group#Properties).2011-02-26
  • 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.