1
$\begingroup$

I know that a finite group with a prime number of elements is cyclic and every element in the group is a generator for the group.

Thinking about $(\mathbb{Z}_p^*, \cdot)$ I thought that the order of $(\mathbb{Z}_p^*, \cdot)$ was $p$, so that every element in the group had to be a generator, but then I pondered the fact that I had to remove the 0 and so $(\mathbb{Z}_p^*, \cdot)$ had to have cardinality $p-1$, and so the theorem shouldn't be applied anymore.

This also explained to me the presence in $(\mathbb{Z}_p^*, \cdot)$ groups (lets say $(\mathbb{Z}_{19}^*,\cdot)$) of particular elements which generate the entire group named "primitive roots" (the group generators if I understood well), and that not every element of the group is a primitive root.

Is all that I wrote correct? Did I make the correct reasoning?

$\endgroup$
  • $\begingroup$ You are right, $\mathbb{Z}_p^\ast$ has $p-1$ elements, so almost always we cannot deduce immediately that the group is cyclic. Indeed it is cyclic, but this requires proof, and the proof takes more than a little work. Because of this, I find the "this explained" part puzzling, since the existence of primitive roots is not obvious. $\endgroup$ – André Nicolas Jun 26 '16 at 22:43
  • $\begingroup$ I maybe explained myself bad: I read from another book (written tofether with an intuitive explanation rather then a formal proof) that in $(\mathbb{Z}_p^*, \cdot)$ there were primitive roots that generated the group $\endgroup$ – Alessio Martorana Jun 26 '16 at 22:54
  • $\begingroup$ It is true that there are primitive roots modulo $p$ for every prime $p$, and also for $p^n$ and $2p^n$ when $p$ is an odd prime. $\endgroup$ – André Nicolas Jun 26 '16 at 22:58
  • $\begingroup$ Yes, the same sentence of the book =) $\endgroup$ – Alessio Martorana Jun 26 '16 at 23:00
1
$\begingroup$

You are correct. The order of $\mathbb{Z}_p^*$ is $p-1$, so it is not a priori cyclic. However, it turns out to be a nontrivial fact that it is cyclic; and not every element is a generator, because (for instance) 2 divides $p-1$ and so there is an element of order $2$.

Actually finding a generator is very difficult in full generality. As far as I know, it's still open whether $2$ is a generator mod $p$ for infinitely many $p$.

$\endgroup$
  • $\begingroup$ Finding the generator is easy: most things are generators. Just try things until you find one; either in order or randomly chosen, and you're nearly guaranteed to pick one after a handful of tries. The only time things get difficult is when $p-1$ is difficult to factor, because you need to know the factorization to fully prove if something generates (but not if you just want to be almost completely sure). $\endgroup$ – user14972 Jun 26 '16 at 22:50
  • $\begingroup$ @Hurkyl I've added a "full generality" rider. $\endgroup$ – Patrick Stevens Jun 26 '16 at 22:51
  • $\begingroup$ Thanks a lot for the answers, is this fact someway related to DLP? $\endgroup$ – Alessio Martorana Jun 26 '16 at 22:56
  • 1
    $\begingroup$ @AlessioMartorana: Sort of related. But in the discrete logarithm problem, you already know a generator $g$, and given $a$ you want to find $k$ such that $g^k=a$ (in the group). $\endgroup$ – André Nicolas Jun 26 '16 at 23:01
  • 1
    $\begingroup$ Don't worry!! And thank you so much anyway just for the first answer! =) P.S. I think it's strictly related to DLP because it's used in RSA encryption/decryption scheme which is based on a large number prime factorization $\endgroup$ – Alessio Martorana Jun 26 '16 at 23:03

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.