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.

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, 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.

• Oh, you're good. I need to read this closely. After just skimming your answer... I don't suppose if you know whether or not this information has been applied to the discrete logarithm problem?
– DAS
Aug 23, 2015 at 20:31
• @DAS: Note that when there is a definite $t$, you need some discrete logarithm to take the squareroots, so the state of the art remains as you know it. Aug 23, 2015 at 20:49

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.

• That's precisely one of the things I was afraid of.
– DAS
Aug 23, 2015 at 19:32

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$.