Iterated square roots over finite field. When do we hit a nonresidue? Suppose that we are working within the integers modulo $p$ where $p$ is some odd prime number. Suppose that $x_0$ is a (nonzero) quadratic residue mod $p$ then there exists some $x_1$ such that $x_1^2 \equiv x_0 \pmod{p}$. Let $x_1$ be such a root of $x_0$. Now, if $x_1$ is also a quadratic residue mod $p$ then we can let $x_2$ be such that $x_2^{2} \equiv x_1 \pmod{p}$. Suppose that we repeat this $n$ times so we have $x_n^2 \equiv x_{n-1} \pmod{p}$, or if you prefer $x_n^{2^n} \equiv x_0 \pmod{p}$.
Is there anyway to determine, without calculating all roots in the field, if, by continuing this process of taking square roots, we will eventually run into some $m$ such that $x_m$ is not a quadratic residue mod $p$? Conversely, is there some $l$ such that if $x_l$ is also a quadratic residue then we can conclude that no such $m$ exists? In both cases, can we obtain any type of bounds on the $m$ and $l$ better than 'less than (p-1)/2'? 
Thank you for your time and consideration. I hope you're having a wonderful day.
 A: I suppose that $p$ is odd and that we start with a nonzero
quadratic residue $x$.
Proposition:


*

*If $p\equiv3\pmod{4}$, the iteration can run endlessly, or be terminated
at any step, depending on which squareroot is chosen.

*If $p\equiv1\pmod{4}$ and the order $m$ of the starting square is even,
then the squareroot iteration ends exactly after $t$ steps,
regardless of intermediate sign choices,
with $t$ being the positive integer such that 
$2^t$ divides $\frac{p-1}{m}$ with odd cofactor.

*If $p\equiv1\pmod{4}$ and the order of the starting square is odd,
then the squareroot iteration can run endlessly, or at any step be led
to a deterministic end in the form of an even-order square,
depending on which squareroot is chosen.


Remark:
For the treatment here, odd factors in the order $m$ of $x$ are irrelevant.
So one might as well write $p-1=2^r u$ with $u$ odd,
then set $m$ to the order of $x^u$ which now must have the form $2^j$
with nonnegative integer $j<r$, equality excluded because $x$ is a square.
Thus $m$ is odd if and only if $j=0$, that is, $x^u\equiv1\pmod{p}$.
Otherwise $m$ is even and $t=r-j$.
Proof:
If $\left(\frac{-1}{p}\right)=-1$, that is, $p\equiv3\pmod{4}$,
then exactly one of the roots is a quadratic residue.
When raising quadratic residues to some power,
exponents are equivalent modulo $m=\frac{p-1}{2}$.
For $p\equiv3\pmod{4}$ we find $m$ is odd, so there is an integer exponent $h\equiv2^{-1}\pmod{m}$, namely $h=\frac{p+1}{4}$,
and raising a quadratic residue $x$ to the $h$-th power modulo $p$
gives one squareroot of $x$.
Now since $x$ is a quadratic residue modulo $p$, so is $x^h$. Therefore, the exponentiation-based way of squareroot finding always yields a root that is a quadratic residue.
Consequently, For $p\equiv3\pmod{4}$, the process of iterating squareroots
based on taking $h$-th powers never runs into a quadratic nonresidue.
On the other hand, if you reserve the choices as to which of the two
possible roots to use, you can choose the nonresidue $-x^h$ instead of $x^h$
after any step you like,
and thus terminate the iteration whenever you want.
This leaves the case $\left(\frac{-1}{p}\right)=+1$, that is,
$p\equiv1\pmod{4}$, for consideration.
In that case, either none or both roots of $x\pmod{p}$
are quadratic residues.
Suppose the order $m$ of $x$ in $(\mathbb{Z}/p\mathbb{Z})^\times$
is even. Given that $x$ is a quadratic residue and
$(-1)^{(p-1)/m} \equiv \left(x^{m/2}\right)^{(p-1)/m}
\equiv x^{(p-1)/2} \equiv +1\pmod{p}$
we find that $\frac{p-1}{m}$ is even.
Let $t$ denote the positive integer such that
$2^t$ divides $\frac{p-1}{m}$ with odd cofactor.
Since $m$ is even, we know that $2^t$ divides $\frac{p-1}{2}$.
I have to use discrete logarithms now.
Let $g$ be a generator of $(\mathbb{Z}/p\mathbb{Z})^\times$
and $k$ the least nonnegative integer such that $g^k=x$.
Since $m$ is the least positive integer such that $p-1$ divides $km$,
we know that $2^t$ divides $k$.
We also know that $2(p-1)$ does not divide $km$,
because otherwise $m$ could be halved which would contradict its minimality.
This means that $2^{t+1}$ does not divide $k$,
so $2^t$ is the maximum power of $2$ dividing $k$.
Note that $t$ has been defined independently from $g$.
We conclude that the least $t+1$ binary digits of $k$,
from highest weight to lowest, are exactly $(1,0,\ldots,0)$,
regardless of $g$.
The two squareroots of $x$ can be expressed as
$g^{k/2}$ and $g^{(k+p-1)/2}$.
Accordingly, the discrete logarithms of the roots are
$\frac{k}{2}$ and $\frac{k+p-1}{2}$.
Note that both logs are congruent modulo $\frac{p-1}{2}$
and thus congruent modulo the divisor $2^t$,
therefore both squareroot logs agree in their last $t$ bits
which are exactly $(1,0,\ldots,0)$.
Accordingly, the order of each squareroot will be twice that of $x$,
hence even, so the iteration will not run into other subcases.
Each squareroot iteration step reduces $t$ by one, essentially chopping off the rightmost zero bit in the known $t$-bit pattern of the discrete logs.
The squareroot iteration ends when the least-significant bit
becomes set, and we know that this happens after exactly $t$
squareroot steps.
Finally suppose the order $m$ of $x$ in $(\mathbb{Z}/p\mathbb{Z})^\times$
is odd.
Then the squareroots of $x$ can be given as $\pm x^h$ where $h=\frac{m+1}{2}$,
and as powers of the quadratic residue $x$,
multiplied with a quadratic residue $\pm1$,
those roots are quadratic residues too.
Now $2h-m=1$ implies that $h$ is coprime to $m$,
therefore the order of the squareroot $+x^h$ remains at $m$.
Consequently, choosing $+x^h$ as the squareroot for further iteration
would lead us again to this odd-order case.
Always choosing $+x^h$ therefore never runs into a quadratic nonresidue.
Considering that the order of $-1$ is $2$ and that $m$ is odd,
we find the order of the squareroot $-x^h$ to be $2m$.
Consequently, choosing $-x^h$ as the squareroot for further iteration
would lead us to the even-order case which leads to a deterministic end.
A: You have a finite field of order $p$, and it's multiplicative group is cyclic of order $p-1$.  So there is a generator $\alpha$ for this multiplicative group, and any element of $\mathbb{F}_{p}^{*}$ can be written as $\alpha^{k}$.  It is a quadratic residue iff $k$ is even, in which case it's square roots are $\pm \alpha^{k/2}$ (which can again be written as a power of $\alpha$).
I don't think you can even attain $(p-1)/2$ as a bound on m. For example, consider $\mathbb{F}_{7}$.Notice that $2^{2} = 4$ and $4^{2} = 2$, so you can continue indefinitely.
A: If $x$ has odd order (say, $g$), then $y = x^{(g+1)/2}$ is a square root of $x$.  Also, $y$ has odd order, so you can repeat.
If you took $y = -x^{(g+1)/2}$ instead, you would eventually get to a nonresidue.
Also, remembering that you're working in a finite field makes the problem too hard; theoretically, all you're really asking about is the behavior of division by $2$ in a cyclic group. In fact, you can even decompose the cyclic group as a product $C_{2^k} \times C_m$, where $m$ is odd... and you can ignore $C_m$ completely since nothing interesting happens there: you can always divide by $2$ modulo $m$.
