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.)

Thanks!

howthe 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$