# How "hard" it is to take an e'th root mod p?

I know it's hard to find the $e$th root of a number mod $n=p_1*p_2$, and if it would be possible we could break RSA. But how hard it is to take an $e$th root mod $p$ where $p$ is a prime and $\gcd(e,p-1)=1$?

• Hint: apply the same math as in RSA.
– fgrieu
Dec 15 '15 at 16:51

$$gcd(e,p-1)=1$$ so there exist $$k,t$$ where $$ek+t(p-1)=1$$. Let $$x$$ be the $$e$$-th root of $$y$$, so $$x^e=y \bmod p$$.
$$y^k=x^{ek}=x\cdot {(x^{p-1})}^{-t}=x \bmod p$$.