# Is the discrete root considered a hard problem?

I know that in groups from large prime order the discrete log problem is considered hard. For example, it is hard to compute $$x$$ from $$g^x$$ and $$g$$.

Does the same holds for the root problem? For example, is it hard in such groups to compute $$g$$ from $$g^x$$ and $$x$$?

• Can you efficiently compute multiplicative inverses modulo a prime? Commented Mar 18 at 7:24
• Yes, I can. But how does it help me? The $x^\text{th}$ root of an element $h$ is some $g$ such that $g^x=h$. Commented Mar 18 at 7:43
• Can you modify that equation so that you have $g$ on one side? Commented Mar 18 at 7:48
• @fgrieu-modelectiontime Note that the question specifies that the group has prime order. Commented Mar 18 at 10:01
• $g^n = ?{}{}{}$ Commented Mar 18 at 14:48

After the discussion in the comments, and with the help of @kelalaka I will answer myself.

I will assume that $$p$$, the order of the group $$|G|$$, is prime, and that $$0 \neq x \in\mathbb{{Z}}_{p}$$.

$$p$$ is prime, so we can efficiently compute the multiplicative inverse of $$x$$ modulu $$p$$, that is $$a\in\mathbb{{Z}}_{p}$$ such that $$x\cdot a=1\;mod\;p$$, using the extended Euclid's algorithm (*).

Then, we can raise $$h:=g^x$$ to the power of $$a$$ and get $$h^{a}=(g^x)^{a}=g^{x \cdot a}=g^1=g$$.

(*) How can it be done? Because $$x$$ and $$p$$ are coprime ($$p$$ is prime and $$a\in\mathbb{{Z}}_{p}$$), so the extended Euclid's algorithm finds integers $$y,z\in\mathbb{{Z}}$$ such that: $$xy+pz=gcd(x,p)=1\;mod\;p$$

Subtracting $$pz$$ from both sides we get:$$xy=1\;mod\;p$$, as we wanted.

• Counterexamples to "$p$ is prime, so we can efficiently compute the multiplicative inverse of $x$ modulo $p$" include $(p,x)=(7,21)$ and $(p,x)=(5,0)$.
– fgrieu
Commented Mar 19 at 7:16
• @fgrieu-modelectiontime when was the last time you've been asked to take the zeroth root of something? Commented Mar 19 at 9:51
• You're quite close, but still not correct. Take for example, $g=2$, $x=5$, $p=13$. Then $g^x = 6 \mod p$ and $a = x^{-1} = 8 \mod p$. However $g^{ax}=3 \mod p$. You're looking for $x^{-1} \mod \varphi (x)$. Commented Mar 19 at 14:31
• @limeeattack Thanks! Why mod $\phi(x)$? What is the rule for exponentiation $(a^b)^c$ mod p? Commented Mar 21 at 15:25
• The example of @limeeattack is in fact not a valid counterexample. $\mathbb{Z}_{13}^*$ is not a prime order group. Commented Mar 24 at 14:11