Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If $p \equiv 3 \pmod{4}$ then $p + 1$ is divisible by 4. If we want to take the square root of $a$ mod $p$ then:
$$\left ( \pm a^{\frac{p + 1}{4}} \right)^2 \equiv a^{\frac{p + 1}{2}} \equiv a^{\frac{p - 1 + 2}{2}} \equiv a^{\frac{p - 1}{2} + 1} \equiv a^{\frac{p - 1}{2}} \cdot a \pmod{p}$$
But since $a$ was chosen to be a quadratic residue (otherwise it has no square roots) it follows that: $$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$ And hence the two square roots of $a$ modulo $p$ can in this case be very easily computed as: $$\pm a^{\frac{p + 1}{4}}$$ Unlike the case for $p \equiv 1 \pmod{4}$ which requires more work to find the square roots of $a$ mod $p$. It is still possible, of course, just a bit more involved (e.g. see the Tonelli-Shanks algorithm).
So that could be one possibility. Another possibility is to observe that $p \equiv 3 \pmod{4}$ simply means that $p - 1$ is only divided once by 2, which might be a requirement or a desirable attribute in many contexts.
$\begingroup$
$\endgroup$
When $p \equiv 3 \pmod 4$ then $-1$ is a non-square modulo $p$. This implies that amongst the two square roots of a quadratic residue modulo $p$, one is itself a quadratic residue modulo $p$.
