2
$\begingroup$

Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.