A number $x$ has been encrypted with the RSA encryption to
$x^5 = 16 \mod 35$
What is $x$?
I know that the answer must be 11, but has anyone an idea how to find out x in a systematic way? I could not find such a way to solve it (with public key and privat key). I think there must be another possibility. Thanks in advance!
The public modulus is small enough so that you know the value of $\varphi (35) = 24$. Since the public encryption key is $e=5$ you can find the private decryption key by computing $d = 5^{-1} \mod 24$ (by pure coincidence, this is 5 again). Get out a modular calculator and do this. Now decrypt the message by $16^d \mod 35$. Done.
The point of the RSA system is that there isn't a good method, unless we have a way to factor the modulus.
However, modern computers are powerful enough to be able to factor two-digit numbers in a reasonable time -- in fact you can look up the factors of 35 on the internet and find $35=5\cdot 7$ and therefore $\varphi(35)=(5-1)(7-1)=24$.
This is important because we then know that $x^{24n+1}\equiv x \pmod{35}$ for every $n$ and a7ll $x$. So if you find a $k$ such that $5k\equiv 1\pmod{24}$ you have $x\equiv x^{5k} \equiv (x^5)^k \pmod{35}$ so raising $16$ to the $k$th power will give you $x$.
Solving $5k\equiv 1\pmod{24}$ is modular division, which you can do using the extended Euclidean algorithm.
