# 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<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 $h$ is a power of $x$, and $x$ is a quadratic residue modulo $p$, then so is $h$. In other words, 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 '15 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. – ccorn Aug 23 '15 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 '15 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$.