I am currently studying Diffie-Helman protocol. In my lecture notes I have a generator g=2 and I'm in group $Z_{13}^*$ . There I calculate a remainder cycle from 1 to 12 with $r =g^i \mod 13 \forall i [0,12]$

I do not quite understand the relation between the generator and the group. This is my $Z_{13}^*$:

enter image description here

How is the generator in the multiplication group any different from $Z_{13}^+$?

enter image description here

  • $\begingroup$ I'm not sure what you're asking. Are you wondering why $g = 2$, a generator of $Z_{13}^*$, is also a generator of $Z_{13}^+$ (it is)? If so, have you considered finding all the generators of $Z_{13}^*$, and all the generators of $Z_{13}^+$? $\endgroup$
    – Thomas
    Nov 22 '14 at 11:53
  • $\begingroup$ I don't get the difference between $g$ being generator of $Z_{13}^*$ and $g$ being generator of $Z_{13}^+$ $\endgroup$
    – libjup
    Nov 22 '14 at 12:05
  • $\begingroup$ why are there numbers going up to 18? $\endgroup$ Nov 22 '14 at 12:33
  • $\begingroup$ The (partial) tables are for the commutative monoid $({\mathbb Z_{13_\text h}},*)$ and the Abelian group $(\mathbb Z_{13_\text h},+)$, where $13_\text h=19$, rather than for what's stated. $\;$ By definition $g$ is a generator of a finite group $(S,\circ)$ iff $g\in S$, and any $x\in S$ can be written as $x=g\circ g\circ\dots g\circ g$, for some number of terms. $\;$ Ascertain what group you are working with (including, most importantly, what the group operation is), and apply that definition. $\endgroup$
    – fgrieu
    Nov 22 '14 at 14:12
  • $\begingroup$ Sorry I posted the wrong pictures; I was working in $Z_{19}$ - I updated the graphics $\endgroup$
    – libjup
    Nov 22 '14 at 16:10

$\mathbb{Z}^*_{13}$ is a group with 12 elements, not 13.

A group is defined by a set of elements, and a "law". The law combines two elements and yields a third one within the set. You get a group if the law fulfils some properties (the law is associative, there is a neutral element, each element has an opposite in the group).

$\mathbb{Z}_{13}$ is a group with 13 elements, using "addition modulo 13" as group law. The neutral element is $0$; the opposite of $4$ is $9$ (because $4 + 9 = 13 = 0 \mod 13$).

$\mathbb{Z}^*_{13}$ is a group that uses "multiplication modulo 13" as group law; it contains all the elements that are invertible modulo 13. Since 13 is prime, these are all elements of $\mathbb{Z}_{13}$ except $0$; so you get 12 elements (the integers $1$, $2$,... $12$ modulo $13$). The neutral element is $1$ (multiplying any element by $1$ leaves it unchanged). The opposite (traditionally called "inverse" since the law is called "multiplication") of $4$ is $10$ (because $4\times 10 = 40 = 1 \mod 13$).

A generator for a group is an element $g$ such that applying the law repeatedly on it ultimately yields all the group elements. In $\mathbb{Z}^*_{13}$, $2$ is a generator for the whole group: if you multiply $2$ by $2$ then you get $4$; if you multiply $4$ by $2$ you get $8$; multiply by $2$ again and you get $3$; then $6$, $12$, $11$, $9$, $5$, $10$, $7$, then $1$. You got all 12 elements. On the other hand, $8$ is not a generator for the whole group since it generates only $8$, $12$, $5$ and $1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.