Principal Square Root mod

Question

"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

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

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

Answer 1

Hope http://www.mersennewiki.org/index.php/Modular_Square_Root helps. I don't know much about the field but it looks like what you're asking. Are you sure you couldn't find it on Google?

Answer 2

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