Is there a method for finding a primitive element (generator) of $(\mathbb Z/p\mathbb{Z})^*$, where $p$ is a prime number?
Finding a generator of $(\mathbb Z/p\mathbb{Z})^*$
4
$\begingroup$
number-theory
group-theory
finite-groups
-
0you mean a primitive root of unity? – 2012-01-14
-
0No i mean: A group G which contains an element a with maximum order ord(a) = |G| is said to be cyclic. Elements with maximum order are called primitive elements or generators. – 2012-01-14
-
0But you referred to Zp specifically. Why not 1? – 2012-01-14
-
0What do you mean with "Why not 1?". – 2012-01-14
-
0you mean Zp, the group of integers modulo p, under the operation of addition modulo p, right? 1 is a generator for that group. – 2012-01-14
-
2No I mean Zp in respect of multiplication modulo p. – 2012-01-14
-
1That is, the group of nonzero integers mod p, under multiplication mod p. Then you are asking for primitive roots of unity mod p! – 2012-01-14
-
2http://en.wikipedia.org/wiki/Primitive_root_modulo_n – 2012-01-14
-
2The same link you have provided contains a detailed answer you are looking for, see [this](http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots) @gosom – 2012-01-14
-
4The references provided in that article should provide further methods. I've that Cohen's book is pretty good, for example. – 2012-01-14
-
1Check out Section 4.8 (computing n-th primitive root of unity) in *Algorithms For Computer Algebra* by Keith O. Geddes, Stephen R. Czapor, George Labahn. – 2012-01-14
-
0If $p$ is of the form $2^\alpha + 1$ then the primitive elements are precisely the quadratic non-residues – 2012-05-22