Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.