Solving a congruence with high numbers and computing the Legendre symbol I am asked to compute $\left(\frac{77}{257}\right)$ specifically using Euler's criterion. I have manged to get the following:
$$\left(\frac{77}{257}\right)\equiv77^{256/2} \bmod257$$
$$\equiv77^{128}\bmod257$$
I don't know where to go from here as I don't know the trick to simplify congruences that are big like this without typing it in on an online calculator. I believe it may be to do with pulling out factors to reduce the size of $77^{128}$ but am not sure. Can anyone help me?
 A: $77^{128}\pmod{257}$ is simple to compute through repeat-squaring:


*

*$77^{2}\equiv 18\pmod{257}$

*$77^{2^2}\equiv 18^2 \equiv 67\pmod{257}$

*$77^{2^3}\equiv 67^2\equiv 120\pmod{257}$

*$77^{2^4}\equiv 120^2\equiv 8\pmod{257}$

*$77^{2^5}\equiv 8^2 \equiv 64\pmod{257}$

*$77^{2^6}\equiv 64^2\equiv 241\pmod{257}$

*$77^{2^7}\equiv 241^2\equiv\color{red}{-1}\pmod{257}$


hence $77$ is not a quadratic residue $\!\!\pmod{257}$.

Quadratic reciprocity is way more efficient:
$$\left(\frac{77}{257}\right)=\left(\frac{-180}{257}\right)=\left(\frac{5}{257}\right)=\left(\frac{2}{5}\right)=\color{red}{-1}.$$
A: The modulus of 257 was deliberately chosen in this case – the exponent is then 128, a power of two, and exponentiation by squaring will get you there quickly. 
$$77^2\equiv18\bmod257$$
$$77^4\equiv18^2\equiv67\bmod257$$
$$77^8\equiv67^2\equiv120\bmod257$$
$$77^{16}\equiv120^2\equiv8\bmod257$$
$$77^{32}\equiv8^2\equiv64\bmod257$$
$$77^{64}\equiv64^2\equiv-16\bmod257$$
$$77^{128}\equiv(-16)^2\equiv-1\bmod257$$
Therefore
$$\left(\frac{77}{257}\right)=-1$$
Variants on this procedure are used in practice to perform the modular exponentiations that underpin the RSA cryptosystem.
