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 '19 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 '19 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 '19 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 '19 at 7:32

Your Answer

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

Browse other questions tagged or ask your own question.