0
$\begingroup$

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

$\endgroup$
18
  • 1
    $\begingroup$ Can you efficiently compute multiplicative inverses modulo a prime? $\endgroup$
    – Maeher
    Commented Mar 18 at 7:24
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Mar 18 at 7:43
  • 1
    $\begingroup$ Can you modify that equation so that you have $g$ on one side? $\endgroup$
    – Maeher
    Commented Mar 18 at 7:48
  • 1
    $\begingroup$ @fgrieu-modelectiontime Note that the question specifies that the group has prime order. $\endgroup$
    – Maeher
    Commented Mar 18 at 10:01
  • 1
    $\begingroup$ $g^n = ?{}{}{}$ $\endgroup$
    – kelalaka
    Commented Mar 18 at 14:48

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – fgrieu
    Commented Mar 19 at 7:16
  • 1
    $\begingroup$ @fgrieu-modelectiontime when was the last time you've been asked to take the zeroth root of something? $\endgroup$
    – Maeher
    Commented Mar 19 at 9:51
  • 1
    $\begingroup$ 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)$. $\endgroup$ Commented Mar 19 at 14:31
  • $\begingroup$ @limeeattack Thanks! Why mod $\phi(x)$? What is the rule for exponentiation $(a^b)^c$ mod p? $\endgroup$ Commented Mar 21 at 15:25
  • 1
    $\begingroup$ The example of @limeeattack is in fact not a valid counterexample. $\mathbb{Z}_{13}^*$ is not a prime order group. $\endgroup$
    – Maeher
    Commented Mar 24 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.