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?

  • $\begingroup$ This might be helpful Find the generators of multiplicative group of units efficiently? $\endgroup$ – kelalaka Feb 9 at 19:18
  • 3
    $\begingroup$ @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$)? $\endgroup$ – yyyyyyy Feb 10 at 18:08
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Feb 12 at 17:56
  • $\begingroup$ 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. $\endgroup$ – fgrieu Feb 13 at 7:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.