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.
I suppose that $p$ is odd and that we start with a nonzero quadratic residue $x$.
Proposition:
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.