TITLE: Principal Square Root mod
QUESTION [1 upvotes]: "Theorem: let p be a prime satisfying $p=3\bmod4$. Then for an integer y which is a square modulo p, $x=y^{(p+1)/4}\bmod p$ is a square root mod p of y.  That is, $x^2=y\bmod p$. This is called the principal square root of $y$.
I don't know really know how to get started..do I have to find a prime $p$ satisfying each of these? How would I go about doing that?
So I am using the first answer in this http://www.math.umn.edu/~gennady/cryptosolutions7.pdf as a guide

Find the principal square root of 2 mod 19

$19=3\bmod4$
$p=19$ and $y=2$
$x=2^{(19+1)/4}\bmod 19$
$x=2^{5}\bmod 19$
$x=13$

Find the principal square root of 6 mod 19

$19=3\bmod4$
$p=19$ and $y=6$
$x=6^{(19+1)/4}\bmod 19$
$x=6^{5}\bmod 19$
$x=5$
I have no idea if these answers are right...

REPLY [1 votes]: The principle square root $x$ of $y$ is given by the formula $x=y^{(p+1)/4}\bmod p\;$ if y is a quadratic residue. Additionally there is another square root, namely $-x$.
Your first example shows that the formula gives valid square roots only if $y$ is a QR $\bmod 19$, which is not the case for $2\pmod{19}\;$ and therefore $13^2=169\equiv 17 \equiv -2 \not \equiv 2 \pmod {19}.$ 
On the other hand $6$ is a QR $\bmod 19,\,$ and 5 really is a square root $5^2=26\equiv 6 \pmod {19}$.
The principle square roots have some importance in cryptography, see 
Blum integers and the cryptographic links there (search for Blum in the freely available HAC).
{"set_name": "stack_exchange", "score": 1, "question_id": 1027909}