Iterated square roots over finite field. When do we hit a nonresidue?

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.

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.