Algorithm to find square root of a quadratic residue mod p

[tjkubo]

I'm going through an explanation in a number theory book about Tonelli's algorithm to find the square roots of a quadratic residue modulo $p$ where $p$ is prime, i.e. I want to solve $x^2 \equiv a \pmod{p}$ with $(\frac{a}{p}) = 1$. The book goes as follows:

Let $p - 1 = 2^s t$, where $t$ is odd.

By Euler's criterion, $A^{2^{s-1}} \equiv 1$ where $A = a^t$, so the order of $A$ divides $2^{s-1}$.

Let $d$ be a quadratic nonresidue mod $p$ and $D = d^t$.

By Euler's criterion, $D^{2^{s-1}} \equiv -1$ so the order of $D$ is exactly $2^s$. Similarly, the order of $D^{-1}$ is $2^s$.

Since the group $U(p)$ of units mod $p$ is cyclic, $A$ is in $\langle D^{-1} \rangle$, the cyclic subgroup generated by $D^{-1}$. Moreover, $A \equiv D^{-2u}$ where $u$ is some integer $0 \leq u < 2^{s-1}$.

Then, $a^tD^{2u} \equiv 1$, so $a^{t+1}D^{2u} \equiv a$. Thus, a solution is $x \equiv a^{(t+1)/2}D^u$.I got stuck where it says $A$ is an even power of $D^{-1}$. Can someone explain this?

 

[coquelicot]

Note1 : the sentence "since the group U(p) of units modulo p is cyclic" is very confusing in my opinion. The right justification should be: if w is a primitive root modulo p, then w^t is of order 2^s and generates all the elements of order dividing 2^s. So, the group of all such element is cyclic of order 2^s. Since D is of order 2^s, D^{-1} is a generator of this group.

Note2 : the answer to your question is: let A = D^{-\alpha}, with 0\leq \alpha\leq 2^s. Since the order of A divides 2^{s-1}, say 2^i, and since the order of D^{-1} is 2^{s}, there holds -\alpha 2^i = k2^s, with i\leq s-1. Hence \alpha is multiple of 2, say \alpha = 2u, with 0\leq 2u\leq 2^s. Hence u\leq 2^{s-1}.

 

[tjkubo]

Thank you for clarifying.

I wonder why my book made that last inequality a strict one, since that would just lead to $x = - a^{(t+1)/2}$ which is also a solution.