# Square root of 5 in modulo prime field

How can we efficiently find square root of 5 in a mod prime field. By quadratic reciprocity we can argue that 5 is a square in modulo p(prime) is p is square modulo 5. But how exactly can we calculate it.

-

One way to approach this is to note that $5$ has a square root only in primes of the form $5n\pm 1$, and that half of these 5 will have an odd period (ie 11, 19 mod 20).

For all primes of the form $p = 5n\pm 1$, 5 has a square root. It also means, that where $5^\lambda=1 \pmod p$, then $\frac{p-1}\lambda$ is even. We don't need to evaluate $\lambda$, but to simply note that if $\frac{p-1}2$ is odd, then $\frac{p+1}2$ is even. We note further, that $5^{\frac{p+1}2}=5 \pmod p$, and hence $5^{\frac{p+1}4}=\sqrt{5} \pmod p$. For primes of the form $p=11, 19 \pmod {20}$, then $\frac{p-1}2$ is odd, and this process suffices to find the square root directly.

The trick for $p=11, 19 \pmod {20}$, is that $p$ has a period of odd length in base $5$, and so if $p \mid 5^o - 1$, then $p \mid 5^{o+1} - 5$, Since $o+1$ is even, its half must give the square root of 5 directly.

For example, with 11, we see that $5^{\frac {11+1}4}$ gives $5^3=4 \pmod{11}$, where $4^2 = 5$. Likewise, with $19$, $5^{\frac{19+1}{4}}=3125 = 9 \pmod{19}$, and $9^2 = 5 \pmod{19}$.

It will work for the others at varying random levels (a reasonable probability, indeed), and is certianly worth the shot before trying something fancier, like hunting down some $x^2=5$. For example, it works with $p=1, 9 \pmod{20}$ with a fair direct hit rate, and is certianly worth the try before other methods are called for.

For primes of the $p=1,9 \pmod{20}$, one assumes first an odd period, so one divides out all of the powers of $2$ in $p-1$, and add 1, and divide that by $2$, to find the power to try. For example, with $3121$, then $3120$ gives $16\cdot 195$, and $(195+1)/2 = 98$. If it does not work for $98$, then you have to hunt it down some other way.

For example, with $3121$, one finds that $5^{98} = 256 \pmod{3121}$, and that $256^2 = -5 \pmod{3121}$. While it's not $+5$, it is much easier to hunt down $a^n=-1 \pmod p$, and thus this would give a fast solution.

This one works on where primes of the form $p = 4n+1$ (n odd). Since the period in base 5 divides 2n, then $5^n = \pm 1$, and $5^{n+1}=\pm 5$. So it is square root is $5^{(n+1)/2} = \sqrt{\pm 5}$. It follows also that $2^n = \sqrt{-1}$ always, so we can calculate $\sqrt{5}$ directly.

In fact, for $p=21, 29 \pmod{40}$, raising $5^{((p+3)/8)} = \sqrt{\pm 5} \pmod p$ will give either a direct hit, or failing that multiply it by $\sqrt{-1} = 2^{\frac {p-1}4} \pmod p$ will get the answer.

example: for $p=229$, we get $5^{29} = 192$, $192^2 = 224 = -5$. We need to find the square root of $-1$, by $2^{228/4}$, gives $122$, and $122 \cdot 192 = 66$, where $66^2 = 5$.

There are perfectly general ways for handling the remaining cases modulo 1, by using a curious trick i devised some years ago. It runs in pretty much logrithmic time too.

For $p = 40n + 1$ or $40n +9$, you can use isopowers, of the form $a\mbox{^^}(n/5)$, where a = 40n or a=40n+10.

One is seeking from the following algorithm, a value of a, for which $a\mbox{^^}n = 2$, and $a \mbox{^^}(n/5)=b$ isn't. This gives a value of b, for which $b+b+1 = \sqrt{5}$.

The algorithm runs like this. This example shows the finding of x^37, modulo p. The values in cols a0, a1 are direct integers, (eg 37), while the remainder of the columns give $t(n)$. The iteration is $a_2 <- a_2^2 - 2$, and $a_5 = a_2 * a_4 - a_3$, and a_6 = a_5 * a_2 - a_4. These are carried down, as $a_3, a_4 <- a_3, a_5 or a_4, a_6. It runs at 2/3 of the speed of exponent powers.  a0 a1 a2 a3 a4 a5 a6 a0 and a1 are n 37 1 1 0 1 2 3 a2 to a6 are actually t(n) 18 0 2 1 3 5 9 1 4 1 5 9 13 The val a1 = mod(a0,2) 4 0 8 5 13 21 a2 = a2 * a2 - 2 2 0 16 5 21 37 t(n-2)+t(n+2) = a2 * t(n) 1 1 32 5 37  For primes of the form 40n + 1, put k= 8n, For primes of the form 40n+9, put k=8n+2. Start with a=3, and seek first$a\mbox{^^}(5k)=2$. If this works, then see if some$b=a \mbox{^^}k \ne 2$. Then, the square root of 5 is$2b+1$. - This is somewhat disorganized, so it's hard to easily tell how general your solution is. Is there anything here besides the well-known formulas for computing square roots mod p when$p \equiv 3 \bmod 4$, or the less well-known method for$p \equiv 5 \bmod 8$, which still leaves the case of$p \equiv 1 \bmod 8$requiring a more general method? – Hurkyl Oct 12 '13 at 11:22 @Hurkyl It relies on creating odd periods. If you find$5^{2n-1}=1 \mod p$, then also$5^{2n}=5$, whence$5^n= \sqrt{5}$. This happens for all primes of form$20n+11,19$. For primes of the form$40n+21, 29$, which are of the form$4n+1$, we note that$5^{2n}=\pm 1$, and hence$5^{n+1} = \sqrt{\pm 5}$, and since for these primes, we have$2^n=\sqrt{-1}$always. This is three quarter of all cases, by nothing fancier than gauss and fermat. – wendy.krieger Oct 12 '13 at 11:32 Right: those are the primes (modulo which$5$is a square) that are$3 \bmod 4$and$5 \bmod 8$. – Hurkyl Oct 12 '13 at 11:41 Yes, but it's pretty general. For any given number$x\$, there are three-quarters of primes that yield directly to this algorithm, although the devil is in the details. For a quarter of primes, you have to do something fancier, but that's the nature of the beast. @Hurkyl – wendy.krieger Oct 12 '13 at 11:46