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.