# How do I use Cipolla's algorithm to compute a square root of $56$ mod $101$

I understand that for the first step, I just have to find an integer $t$ such that $0\leq t\leq 100$ such that $t^2-56$ is not a perfect square mod $101$. I know that to show that $t^2-56$ is not a perfect square mod $101$, I just have to show that $(t^2-56)^{50}-1$ is not divisible by $101$ (right?). I want to pick a $t$ and calculate. The problem is, is that once I plug in $t$, $(t^2-56)^{50}$ is too large for my calculator to handle. So how do I check that given a $t$, $(t^2-56)^{50}-1$ is not divisible by $101$?

(this is a homework question, and we are allowed to use any internet resources). So far, what we have done in class is prove that the group of units of a finite field is cyclic, and of course Fermat's Little Theorem.

-
You keep referring to $p$ without ever telling us what it is. I suppose $p$ is 101? – Gerry Myerson Nov 13 '11 at 23:07
For roughly half the values of $t$ in your range, $t^2-56$ will not be a square mod $p$. So if you just choose values of $t$ any way you like, pretty soon you'll find one for which $t^2-56$ is not a square. So the question is, what goes wrong with the algorithm if $t^2-56$ is a square? Maybe when the algorithm goes wrong, you can abandon that $t$ and try another? – Gerry Myerson Nov 13 '11 at 23:10

You can reduce the powers $\pmod {101}$ as you go along. So if $t=2, t^2-56=-52, (t^2-56)^5=380 204 032\equiv 36 \pmod {101}$ You can take this to the $5^{th}$ power, reduce mod $101$, and square.
OK, but how did you figure out that $380204023\equiv 36$ (mod 101)? – MathTeacher Nov 13 '11 at 23:30