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.
$\begingroup$
$\endgroup$
asked Feb 26, 2011 at 9:57
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
4
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.
answered Feb 26, 2011 at 11:13
-
$\begingroup$ 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? $\endgroup$ Feb 26, 2011 at 11:29
-
$\begingroup$ 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 $\endgroup$ Feb 26, 2011 at 11:48
-
$\begingroup$ 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. $\endgroup$ Feb 28, 2011 at 3:34
-
$\begingroup$ Just wanted to add that the national logarithm problem is "difficult" to solve, but not NP-hard. Needed to mention this to sleep well. $\endgroup$ Nov 8, 2015 at 17:00
$\begingroup$
$\endgroup$
6
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$.
-
$\begingroup$ @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? $\endgroup$ Feb 26, 2011 at 10:38
-
1$\begingroup$ @bala: Yes, in group or prime order you have every element to be a generator. $\endgroup$– anonymousFeb 26, 2011 at 10:41
-
$\begingroup$ @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? $\endgroup$ Feb 26, 2011 at 10:57
-
$\begingroup$ @bala: but for $n=p$ all the numbers $p-1, p-2, \cdots$ are relatively prime to $p$ right? $\endgroup$– anonymousFeb 26, 2011 at 11:02
-
$\begingroup$ @Chandru1 :) Oops. I am starting to feel dumb! Thanks for the effort. I am getting it now. :) $\endgroup$ Feb 26, 2011 at 11:08
$\begingroup$
$\endgroup$
3
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$.
-
$\begingroup$ 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? $\endgroup$ Feb 26, 2011 at 10:30
-
$\begingroup$ @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. $\endgroup$– yunoneFeb 26, 2011 at 10:40
-
$\begingroup$ Almost there. But how do we select generators from multiplicative groups of prime order? Here thanks to you, addition was easy to understand. $\endgroup$ Feb 26, 2011 at 11:16
$\begingroup$
$\endgroup$
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.
