I'm wondering if there are efficient methods to solve equations such as:
$$ x^{30} = 7 \pmod{83} $$
Where the exponent is some arbitrarily high number.
Thanks!
Asked
Active
Viewed 59 times
0
-
1$15\times11\equiv1\bmod82$, so $y^{15}\equiv7\bmod83$ has solution $y\equiv (y^{15})^{11}\equiv7^{11}\equiv64\bmod83$, so $x\equiv\pm8\bmod83$ – J. W. Tanner Dec 14 '20 at 21:18
-
but how is that related to the exponent 30? – derp Dec 14 '20 at 22:16
-
If $y=x^2$, then $y^{15}=x^{30}$ – J. W. Tanner Dec 14 '20 at 22:23