1

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

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

Math Major
  • 2,234
  • I am unfamiliar with the notion "principal square root modulo a number." Could you please explain what this means. – quid Nov 18 '14 at 18:17
  • When we are working modulo a prime, the Tonelli-Shanks algorithm and its relatives are pretty good. Modulo large composites can be much more difficult. – André Nicolas Nov 18 '14 at 18:17

2 Answers2

1

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

gammatester
  • 18,827
  • Isn't this only the case if p = 3 mod 4? Otherwise, the exponent is not an integer. – Paul Oct 15 '16 at 01:02
  • @Paul: You must check that $x$ is a quadratic residue, otherwise you may get spurious square roots! Another example with $p=19, y=3;;$ then $x \equiv 3^{5} \equiv 15 \pmod {19};$ but $x^2 \equiv 16 \not \equiv 3 \pmod {19},,$ i.e. you can always compute $x=y^{(p+1)/4}\bmod p;$ but $x$ is not always a square root. – gammatester Oct 17 '16 at 07:40
0

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?

ghosts_in_the_code
  • 2,022