Suppose we are working in a cyclic group $G = \mathbb{Z}/n\mathbb{Z}$ where $H$ is a cyclic (multiplicative) subgroup of $(\mathbb{Z}/n\mathbb{Z})^\times$, where $g$ is a generator for $H$. Say the goal is to compute a $k$th root of an arbitrary $k$th power $h$ in $H$, where we assume $k$ divides $|H|$. (That is, $h = g^{kx}$ for some unknown $x \in \mathbb{Z}$, and $g^{x + \frac{|H|}{k} \mathbb{Z}}$ is the set of $k$th roots of $h$.) Further, say we want to compute the minimal $k$th root with respect to $g$, in the sense that we want to output $g^{y}$, where $y$ is the smallest $y \in \{0, 1, \cdots, |H| - 1\}$ such that $g^{ky} = h$. (Equivalently, minimality requires $y \in \{0, \cdots, |H|/k - 1 \}$.)

Is the computational complexity of this problem known for various settings of $n$? One setting of $n$ I'm interested in is where $p$ and $n = 2p^c + 1$ are both primes, $|H| = p^c$, and $k = p$. Does there exist, say, a $\mathsf{poly}(\log n)$-time algorithm for this problem? (In particular, computing the discrete log trivially solves the problem and would be too slow.)


  • 3
    $\begingroup$ A generator of the group $\mathbf Z/n\mathbf Z$, which is additive, is not the same thing as a generator of the group $(\mathbf Z/n\mathbf Z)^\times$, which is multiplicative. Edit the start of your question. $\endgroup$
    – KConrad
    Aug 3 at 11:25
  • $\begingroup$ Yes of course – sorry about that! I edited the question to hopefully clarify what I meant to ask. $\endgroup$
    – anon
    Aug 5 at 20:42
  • $\begingroup$ So you are not requiring that $(\mathbf Z/n\mathbf Z)^\times$ itself is cyclic? I don't know why you say competing the discrete log "would be too slow" since you never indicate how the discrete log is computed, and without that you can't say if such an approach is too slow. And did you have a method in mind for even recognizing that an element $h$ of $H = \langle g\rangle$ is a $k$th power in $H$ in the first place (before even trying to compute a $k$th root of it in $H$)? $\endgroup$
    – KConrad
    Aug 6 at 4:25


Your Answer

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