[Math] How to prove algorithm for solving a square congruence when p ≡ 5 (mod 8)

algorithmscongruencesmodular arithmeticproof-verification

I'm having trouble understanding why this algorithm works and where it comes from:

"Suppose p ≡ 5 (mod 8) is a prime and y is a square (mod p); that is, for some $ x, x^2
≡ y\ (mod\ p)$. This can be solved by the following algorithm

  1. Compute $d ≡ y^{(p−1)/4} \pmod {p}$. Show that $d^4 ≡ 1 \pmod {p}$
  2. Hence show $d ≡ ±1 \pmod {p}$ or $d^2 ≡ −1 \pmod {p}$.
  3. If $d ≡ 1 \pmod {p}$ compute $r ≡ y^{(p+3)/8} \pmod {p}$; if $d ≡ −1 \pmod {p}$ compute $r ≡
    2y(4y)^{(p−5)/8}\pmod {p}$;
  4. Then (r, −r) are the square roots of y.
    [We will return to the case $d^2 ≡ −1 \pmod {p}$ later.]"

Here are my attempts:

Since $ p \equiv 5 \pmod {8}$ then $p = 8k + 5$ for some integer $k$. With some algebra I found that $\frac{p-1}{2} = 4k +2 = 2(2k+1)$.
We can let $d \equiv y^{2k+1} \pmod {p}$. So $d^2 \equiv y^{2(2k+1)} \pmod {p}$. Then $d \equiv y^\frac{p-1}{4} \pmod {p}$. And $d^4 \equiv 1 \pmod {p}$ by Fermat's theorem.

For the second step, since $d^2 \equiv y^\frac{p-1}{2} \equiv (\frac yp) \equiv1 \pmod {p}$ by Legendre's theorem. So $d \equiv \pm 1 \pmod {p}$. I'm confused why $d^2$ would equal $-1$ though.

I'm even more confused about the third step. After playing around with it, I found that if we set $r \equiv y^{k+1} \pmod {p}$ and substitute $k = \frac{p-5}{8}$ (since $p = 8k + 5$) then we get the first r, but I have no idea where the $2y$ and the $4y$ came from in the second one.

Any advice, hints, or clarifications? Thanks

Edit: For the second step, since $d^4 \equiv 1 \pmod {p}$, then $d^2 \equiv \pm 1 \pmod {p}$. So either $d^2 \equiv 1 \pmod {p}$ which implies that $d \equiv \pm 1 \pmod {p}$ or $d^2 \equiv -1 \pmod {p}$.

Best Answer

The $d^2 \equiv -1 \pmod{p}$ part is wrong. Presumably, the author mixed some parts of the $p \equiv 1 \pmod{8}$ case in, where one computes $d = y^{(p-1)/8}$.

For $p \equiv 5 \pmod{8}$, we always have $1 = \left(\frac{y}{p}\right) \equiv d^2 \pmod{p}$.

So if $d \equiv 1 \pmod{p}$, we choose $r \equiv y^{(p+3)/8}\pmod{p}$, and that yields

$$r^2 \equiv y^{(p+3)/4} \equiv y\cdot y^{(p-1)/4} \equiv y\cdot d \equiv y \pmod{p}.$$

For $d \equiv -1\pmod{p}$, choosing $r \equiv y^{(p+3)/8} \pmod{p}$ would lead to $r^2 \equiv y\cdot d \equiv -y \pmod{p}$ by the same computation as above, so we mix a square root of $-1$ in to obtain a square root of $y$. For $p \equiv 5 \pmod{8}$, we have $\left(\frac2p\right) = -1$, so $2^{(p-1)/4}$ is a square root of $-1$ modulo $p$. The author just wrote it in an obscure way, we have $2\cdot 4^{(p-5)/8} = 2\cdot 2^{(p-5)/4} = 2^{(p-1)/4}$.

Related Question