Solving a congruence with high numbers and computing the Legendre symbol

Question

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?

Answer 1

$77^{128}\pmod{257}$ is simple to compute through repeat-squaring:

1. $77^{2}\equiv 18\pmod{257}$
2. $77^{2^2}\equiv 18^2 \equiv 67\pmod{257}$
3. $77^{2^3}\equiv 67^2\equiv 120\pmod{257}$
4. $77^{2^4}\equiv 120^2\equiv 8\pmod{257}$
5. $77^{2^5}\equiv 8^2 \equiv 64\pmod{257}$
6. $77^{2^6}\equiv 64^2\equiv 241\pmod{257}$
7. $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}.$$

Answer 2

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.