4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – DAS Aug 23 '15 at 20:31
  • $\begingroup$ @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. $\endgroup$ – ccorn Aug 23 '15 at 20:49
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's precisely one of the things I was afraid of. $\endgroup$ – DAS Aug 23 '15 at 19:32
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.