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

  • $\begingroup$ Please look at how I formatted your last question, math.stackexchange.com/questions/518080/…, and format this one similarly. Hint: $a\equiv b \pmod {n+1}$ is written $a\equiv b \pmod {n+1}$ $\endgroup$ – dfeuer Oct 7 '13 at 21:41
  • $\begingroup$ In 3. And 4., make sure to work out the order of $y$ . $\endgroup$ – user641 Oct 7 '13 at 21:52
  • $\begingroup$ @SteveD I'm not sure I understand what you mean by the order of $y$... $\endgroup$ – Amber Oct 7 '13 at 22:04

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

  • $\begingroup$ do you think you could fix the fractions in your exponents? they are very difficult to read (I think it is in general a good rule to use the "/" notation in fractional exponents). $\endgroup$ – user641 Oct 7 '13 at 23:44
  • 1
    $\begingroup$ I think I could. Yes, you're right (except maybe in offset formulae with larger font). $\endgroup$ – Daniel Fischer Oct 7 '13 at 23:49

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.