# Finding generator element for multiplicative group of order $n$ - feasible?

Given a multiplicative group of order $$n$$, how hard is it to find a generator element (such that all other elements can be expressed as powers of that generator)?

What would be the complexity?

• This might be helpful Find the generators of multiplicative group of units efficiently? – kelalaka Feb 9 '19 at 19:18
• @caffein Since this is tagged "RSA": Are you really interested in a group $G$ of order $n$, or did you mean the multiplicative group $(\mathbb Z/n)^\ast$ of invertible elements modulo $n$ (which never has order $n$)? – yyyyyyy Feb 10 '19 at 18:08
• What does multiplicative mean, beside notation? How exactly are we given the group? Are we given $n$? The neutral? A way to generate other elements in the group? A way to apply the group law on previously given/obtained elements? A way to test equality of elements obtained? Can we obtain the factorization of $n$? As noted above, the tag RSA seems wrong. – fgrieu Feb 12 '19 at 17:56
• Hints: How does knowing the factorization of $n$ help test if an element $g$ is a generator? What is the proportion of generators in the group? What plausible hypothesis in addition to those in my previous comment do we need to obtain an heuristic algorithm yielding a generator ? Note: that algorithm is often used in practice. – fgrieu Feb 13 '19 at 7:32