Quadratic Residue

Given a odd prime $p$ and a quadratic residue $a$, efficiently find $x$ such that $x^2=a$.

One algorithm is the Tonelli–Shanks algorithm. The symbols here are based on this solution.

Sol

If $p=4k+1$, from the condition we know $a^{(2k+1)} = 1\ mod \ p$, then we get $(a^{k+1})^2=a\ mod\ p$, which means we have found a square root.

It is harder when $p=1 \ mod \ 4$. Let $b$ be a quadratic nonresidue. Let $p=m2^s+1$, then let $u_0=a^m,v_0=a^{(m+1)/2}$. Then $v_0^2=au_0$, $u_0^{2^{s-1}} = 1$.

We recursively build two sequences. Now if $u_k=1$, it is done. Otherwise, suppose $u_k^{2^{r_k}}=1$ and $u_k^{2^{r_k-1}} = -1$, let $c=b^m$, then $c^{2^{s-1}}=b^{(p-1)/2}=-1$.

Let $u_{k+1}=u_kc^{2^{s-r_k}}$, $v_{k+1}=v_kc^{2^{s-r_k-1}}$. Then they satisfy $v_i^2 = au_i$ by induction, moreover, $u_{k+1}^{2^{r_k-1}} = (u_{k}^{2^{r_k-1}})(c^{2^{s-1}}) = (-1) \times(-1) = 1$, which means $r_{i+1}<r_i$. Therefore, we can surely get some $u_i=1$ at last and find $v_i^2=a$.

Remark that, by Chinese Remainder Thm, if we can do factoring efficiently, then we can solve this for arbitrary $n$ as a module.