Is there a reasonably simple way to find the square root of $a$ modulo $p$ where $p$ is an odd prime? If the odd prime is small number it seems you can do this by brute force. HOwever if we want to solve something like x^2=2 mod 103 (whose solution is 38 and 65 mod 103) is pretty cumbersome because we have a non-linear Diophantine equation x^2=2+101y. Is there an efficient and quick method to solve something of this kind? If I try primitive roots then the first primitive root is 5 not 2 so that does not help.
Asked
Active
Viewed 1,410 times
2
-
1Please see here on MO. – ə̷̶̸͇̘̜́̍͗̂̄︣͟ Jul 15 '18 at 11:22
-
1Do you know how to do this if p is 3 mod 4? In that case it's very easy: just raise a to the (p+1)/4 modulo p. (Of course this only works if a has a square root mod p.) The above link seems to be showing that it's always efficient, but it is definitely more complicated in the case that p is 1 mod 4. – CJD Jul 15 '18 at 11:47
-
@cjd, fyi. What if you try tovtwke the square root of a residue $r \bmod p$ that isn't a quadratic residue? With $p\equiv 3\bmod 4$ the $r^{(p+1)/4}$ formula gives instead a square root of $-r$. – Oscar Lanzi Jul 15 '18 at 12:33
-
Tonelli–Shanks algorithm – Count Iblis Jul 15 '18 at 14:36
-
1The easy case $p \equiv 3 \bmod 4$ has been discussed in previous Questions, but there is perhaps room on Math.SE for a comprehensive Answer for $p \equiv 1 \bmod 4$ (not just the link to the Wikipedia article, as there are competing algorithms). – hardmath Jul 15 '18 at 19:20
2 Answers
3
Partial answer:
If $p=4n-1$, then let $b = a^{\frac{p+1}{4}}$. Then $b^2=a^\frac{p+1}{2}=a^{\frac{p-1}{2}}a\equiv a$ because of Euler's criterion.
lhf
- 216,483
1
Let $p$ be an odd prime and we can say whether an integer $a$, $a\ne0(\mbox{mod})p,$ has a square root mod $p$ or not by $$\mbox{a is }\begin{cases}\mbox{a quadratic residue if $a^{\frac{p-1}{2}}\equiv 1(\mbox{mod }p)$} \\\mbox{a quadratic nonresidue if $a^{\frac{p-1}{2}}\equiv -1(\mbox{mod }p)$}\end{cases}$$
Key Flex
- 9,475
- 7
- 17
- 34