Square root of 5 in modulo prime field

Question

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.

Answer 1

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