Calculation of Euler’s Criterion
Matthew Barrera 
In order to solve Quadratic Congruences, we need Euler’s Criterion to determine whether the congruence is solvable. My question is, for those huge numbers, how can we determine whether it is congruent to 1 or -1 mod p?
Here is how we define Euler’s Criterion
For example, how can we know whether $2^{30} \equiv 1 (mod 61)$ or $2^{30} \equiv -1 (mod 61)$
$\endgroup$2 Answers
$\begingroup$These numbers are small compared to those actually used e.g. in (RSA) cryptography. They are computed withModular_exponentiation. An alternative is to use fast algorithms for the Jacobi/Legendre symbol.
You are right in your second comment: to test whether $2$ is a quadratic residue mod $61$ you just have to look at property (8) in the Wiki reference and get $\left(\frac{2}{61}\right) = -1\;$ because $\;61 \equiv 5 \pmod 8.$ Thus computing Jacobi symbols for $a=2$ is trivial.
Here is the modular computation using the right-to-left binary method, all steps are $\bmod 61$ $$2^{30} \equiv 2^{16} \times 2^8 \times 2^4 \times 2^2$$ $$2^2\equiv 4, \quad 2^4\equiv16, \quad 2^4 \times 2^2 \equiv 64 \equiv 3$$ $$2^8\equiv16^2\equiv12, \quad2^8 \times 2^4 \times 2^2 \equiv 12\times 3 \equiv 36$$ $$2^{16} \equiv 12^2 \equiv 22, \quad 2^{16} \times 2^8 \times 2^4 \times 2^2 \equiv 22\times 36 \equiv 60 \equiv -1$$
$\endgroup$ 2 $\begingroup$I would only use Euler for being able to say something about these large numbers, not prove that $(\frac{2}{61})=-1$ from solving these large numbers.
So, $(\frac{2}{61})=-1$ because (see Using gauss's lemma to find $(\frac{n}{p})$ (Legendre Symbol)) $61 \equiv -3 \mod 8$. From Euler it follows then that $2^{30} \equiv -1 \mod 61$. No complications whatsoever.
Moral: use Gauss' lemma to determine the value of $(\frac{a}{p})$, then use that value and Euler to derive which of $a^{\frac{p-1}{2}} \equiv \pm 1 \mod p$ holds.
$\endgroup$
